0
$\begingroup$

List of problems I'm interested in:

  1. $\oplus$SAT

  2. #SAT-decision

  3. Permanent-decision (YES if permanent is greater than given number $k$)

I have discovered poly-reduction for MAJSAT (and MAJQBF). However, I don't know such reduction (practical) for these problems.

How can I solve any of these problems with polynomial runs of TQBF? Or can I make a special TQBF to solve them. The special TQBF length should increase (not more than) polynomially compared to original problem.

Improve this question
$\endgroup$
12
  • $\begingroup$ If you know they can be solved with polynomial space, then they are in PSPACE, and thus if P=PSPACE, they can also be solved in polynomial time $\endgroup$
    – Ariel
    May 11, 2017 at 10:31
  • 1
    $\begingroup$ The proof for TQBF being PSPACE complete is constructive, i.e. it constructs a reduction from an arbitrary $L\in\mathsf{PSPACE}$ to TQBF. So yes, such a reduction is known. $\endgroup$
    – Ariel
    May 11, 2017 at 10:55
  • 1
    $\begingroup$ I don't know what "practical reduction, not theoretical" means, but you can definitely take the reduction from the proof, and code it in any language you like. You can find the proof here zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf $\endgroup$
    – Ariel
    May 11, 2017 at 11:16
  • 1
    $\begingroup$ Welcome to CS.SE! We prefer that you ask one question per post (i.e., rather than asking about a list of problems, ask about a single problem; and rather than saying you're interested in them, ask a specific question about them). That works better with this site's format. If you have multiple questions, you can ask them separately in multiple posts. Finally, what do you mean by "poly-reduction"? Do you mean polynomial-time reduction? What do you mean by "reduction (practical)"? Does that mean that polynomial-time isn't good enough? $\endgroup$
    – D.W. ♦
    May 11, 2017 at 14:40
  • 1
    $\begingroup$ Please edit the question accordingly. We prefer that you edit the question so that all relevant information is contained in the question itself, not in the comments, and that the question reads well and is clear for someone who reads it for the first time. People shouldn't have to read the comments to understand what you are asking. I still can't understand what you are asking, and I can't understand your sentence defining poly-time reduction. The notion of a polynomial-time reduction has a standard accepted meaning. Are you using the term in a different way? $\endgroup$
    – D.W. ♦
    May 11, 2017 at 15:24

1 Answer 1

Reset to default
2
$\begingroup$

The reduction you refer to is called Turing reduction. Given $A,B\subseteq \Sigma^*$, we say $A\le_T B$ if there exists a polynomial time Turing machine which decides $A$, given oracle access to $B$. You might call this practical, and in some sense this is the natural way to say $A$ is no harder than $B$ (give me a program for $B$, and i'll write an efficient program for $A$ which uses the previous program as a subroutine).

The standard notion of reduction in complexity theory is Karp reduction (also called many to one reduction). We say $A$ is reducible to $B$ in this sense, if there exists a polynomial time computable function $f$ such that $x\in A \iff f(x)\in B$. Note that this is a weaker condition, i.e. if $A$ is Karp reducible to $B$, it is also Turing reducible to $B$ (apply $f$ on the input, and query the oracle on the result).

Since TQBF is PSPACE complete, then by definition, every language in PSAPCE has a Karp reduction to it (and thus also a Turing reduction). Not only that we know there exists such a reduction, but given a PSPACE machine for some language $L$, then we know how to construct a reduction from $L$ to TQBF (this is done in the proof for the PSPACE completeness of TQBF).

The decision versions of $\#P$ problems are in PSPACE, since you can go over all possible witnesses and count how many are accepting (the only thing you need to store is the counter). This means that all such problems are reducible to TQBF. This is a very precise statement, but intuitively, it says exactly what you want it to. If you can efficiently decide TQBF, then you can efficiently decide all languages in PSPACE, which includes the decision versions of #SAT and permanent.

Improve this answer
$\endgroup$
6
  • $\begingroup$ But number of witnesses is exponential, right? And thus it will take exponential runs of TQBF, no? Still poly-space, but not time. $\endgroup$
    – rus9384
    May 11, 2017 at 18:05
  • $\begingroup$ It seems you don't have a good grasp on the notion of polynomial reductions yet. I covered it in my answer, review the definitions carefully. One run is enough, this is exactly the meaning of TQBF being PSPACE complete under Karp reductions. $\endgroup$
    – Ariel
    May 11, 2017 at 19:33
  • $\begingroup$ So, if it takes a single run, let's say, if TQBF is solvable in $O(n^2)$ time, #SAT is also solvable in $O(n^2)$ time? Or can it be possible that the best bound for #SAT may be $O(n^4)$ or any other polynom? $\endgroup$
    – rus9384
    May 11, 2017 at 19:43
  • $\begingroup$ The bound might be worse, depending on the runtime of the reduction. $\endgroup$
    – Ariel
    May 11, 2017 at 20:03
  • $\begingroup$ Worse than $O(n^4)$ or worse than polynom? $\endgroup$
    – rus9384
    May 11, 2017 at 20:09

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.