23
$\begingroup$

Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ benefit from this oracle access. Of course, the speed-up in $\bf P$ cannot be super-polynomial, but it can still be polynomial. For example, could we find a shortest path faster with a $SAT$ oracle, than without it? How about some more sophisticated tasks, such as submodular function minimization or linear programming? Would they (or other natural problems in $\bf P$) benefit from a $SAT$ oracle?

More generally, if we can pick any problem in ${\bf NP}-{\bf P}$, and use an oracle for it, then which of the problems in $\bf P$ could see a speed-up?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ How fast is the oracle? If it takes $O(s)$ time, more problems can be sped up than if it takes $O(s^5)$ time, where $s$ is the size of the SAT formula. $\endgroup$
    – Peter Shor
    Sep 28, 2015 at 17:24
  • 2
    $\begingroup$ @PeterShor I assume that the oracle, upon receiving a SAT formula as a query, returns a YES or NO answer, signifying whether the formula is satisfyable or not, in a single step (constant time). This is independent of the formula size. Of course, the formula has to be constructed in order to be queried. This construction time is not independent of the formula size, and it is also problem dependent which formulas need to be queried. But once the formula is constructed, receiving the answer is counted as a single step, for any formula. $\endgroup$
    – Andras Farago
    Sep 28, 2015 at 20:50
  • 3
    $\begingroup$ If instead of a SAT oracle you allowed a $\Sigma_2 SAT$ oracle, then it could be used to find minimal circuits for any problem. This would give a nearly optimal amortized cost to any problem (the reason it's only amortized is that if you only use this once, then the size of the $\Sigma_2 SAT$ formula you write down is essentially the runtime of your original poly-time algorithm - but after that step you then have an optimal circuit for all instances of size $\leq n$). $\endgroup$
    – Joshua Grochow
    Sep 28, 2015 at 23:10
  • $\begingroup$ @JoshuaGrochow Your comment is very interesting! It would be great to see it as an answer, with more details. $\endgroup$
    – Andras Farago
    Sep 29, 2015 at 21:15

3 Answers 3

Reset to default
15
$\begingroup$

Actually, acceptance of nondeterministic Turing machines in time $t$ is $O(t \log t)$-time reducible to SAT (the construction is via oblivious simulation, see Arora-Barak), so typically any time a nondeterministic machine is appreciably faster than a deterministic one, we'll see at least some speedup with a SAT oracle.

To be more concrete, primality testing comes to mind, as the best variant of the AKS algorithm appears to test primality of an $n$-bit number in time $O(n^6 \; \text{polylog}\; n)$. But if we go "old school", Pratt gave a nondeterministic TM to decide primality in time $O(n^3 \; \text{polylog}\; n)$. Acceptance of this machine can be reduced (deterministically) in $O(n^3 \; \text{polylog}\; n)$ time to a SAT instance.

The 3SUM problem may be another example, as it seems like one can guess a solution and check it in subquadratic time, and then acceptance of such a machine can be reduced to SAT in subquadratic time.

Improve this answer
$\endgroup$
7
$\begingroup$

More generally, if we can pick any problem in NP−P, and use an oracle for it, then which of the problems in P could see a speed-up?

This question gets more directly at representation and time required to reduce one problem to another....

The main answer I have in mind is an Integer/Linear Programming oracle. The decision version of that problem is NP-complete. There is a trivial "reduction" from linear programming because it is a special case. But an oracle for linear programming alone (let alone ILP) speeds up many problems that are immediately solvable by linear programming. They can be reduced to it in linear time by rewriting the problem as an LP. For instance, shortest paths and other flow problems, matchings.

But I don't think ILP is the only one by any means, it's probably more that people haven't thought much about e.g. reducing shortest-path to TSP or so on.

Improve this answer
$\endgroup$
3
$\begingroup$

On a related note (more of a comment, posting as an answer by request), if instead of a $SAT$ oracle one allows a $\Sigma_2 SAT$ oracle, then it could be used to find minimal circuits for any problem in $\mathsf{P}$ (this follows the same idea as the proof of Karp-Lipton). This would give a nearly optimal amortized cost to any problem; the reason it's only amortized is that if you only use this once, then the size of the $\Sigma_2 SAT$ formula you write down is essentially the runtime of your original poly-time algorithm, but after that step you then have an optimal circuit for all instances of size $\leq n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I find this answer very interesting, because it shows that an $NP^{NP}$ oracle can be much more useful/powerful than an $NP$-oracle, even for practical problems in $P$! Of course, we knew that $NP^{NP}\neq NP$ (assuming $PH$ does not collapse below the second level), but it seemed like a rather obscure theoretical fact that has nothing to do with $P$. But this perception was wrong, the difference can be essential even for practical problems in $P$. (Too bad that we have neither an $NP$, nor an $NP^{NP}$ oracle...) $\endgroup$
    – Andras Farago
    Oct 1, 2015 at 17:22
  • 1
    $\begingroup$ @AndrasFarago: Interesting point! I wonder if there is any interesting and natural consequence for "practical problems in $\mathsf{P}$" of having oracles higher up in $\mathsf{PH}$. My initial guess would be that we don't really know, related to the fact that we don't really know how to use more than a few quantifier alternations very well: cstheory.stackexchange.com/a/11403/129 $\endgroup$
    – Joshua Grochow
    Oct 1, 2015 at 22:23
  • $\begingroup$ @ JoshuaGrochow A problem using a higher level oracle from PH could look like this. Find a minimum size circuit that correctly solves the original problem. Among the min size circuits (there may be exponentially many), find one that has maximum energy efficiency (with some definition of energy efficiency). Among the resulting circuits (possibly still exponentially many), find one that has minimum depth. And so on, alternately minimize/maximize various objective functions, possibly many of them. I think, for $k$ nested min/max optimizations we would need a level $k+2$ oracle from PH. $\endgroup$
    – Andras Farago
    Oct 2, 2015 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.