Optimization of query, version 8.0.5 of Oracle

I have to optimize a query with lots of EXISTS and NOT EXISTS clauses. I know that from 8i I can use HASH_AJ and HASH_SJ for that case, but the database is 8.0.5 and RULE based optimizer is used.
All the columns in the EXISTS and NOT EXISTS are indexed, but the query is very slow, even if AUTOTRACE showing that physical reads = 0.

Any ideas what can I do?

If the sub query involves small table then you can use IN clause rather than EXISTS. This is a general rule. In order to understand your problem correctly, post the SQL and the explain plan output.