Questions about relationships between complexity classes.

learn more… | top users | synonyms

2
votes
1answer
62 views

Is FNP = FEXPTIME if and only if NP = EXPTIME?

It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia). Is it also true that if $\sf ...
-3
votes
1answer
56 views

exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

this new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
8
votes
0answers
69 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
3
votes
1answer
78 views

Is there a largest class of halting programs?

The halting problem says that a Turing machine cannot decide if another Turing machine halts. However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO ...
2
votes
1answer
110 views

Are there any PSPACE problems that don't exist in NP-Hard?

The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it ...
4
votes
2answers
126 views

Is the complexity class NP computably enumerable?

The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing ...
1
vote
3answers
213 views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
1
vote
1answer
97 views

Inclusion of complexity classes (Deterministic Turing Machine)

I can't understand what my professor wrote about these inclusions concerning deterministic classes: $$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$ I understood ...
4
votes
1answer
57 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.
1
vote
1answer
29 views

Is Simon's problem a good NP-intermediate candidate?

We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$ (Though we have the proof that BQP $!=$ BPP with an oracle) Since Simon's problem (as factoring) it's easily solvable by a ...
3
votes
1answer
62 views

Why is the Boolean hierarchy contained in the class $P^{NP}$?

My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P_2\cap\Pi^P_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince ...
0
votes
1answer
27 views

Deterministic Multi-tape Turing Machine construction

I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$: $$L = \{ www \mid w \in \{a,b\}^+ \}$$ I'm not sure how to ...
2
votes
1answer
109 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
4
votes
1answer
32 views

Counting approximate solutions

Many of us are familiar with the $P$ class. Counting solutions is believed to be a difficult task and that is why we usually end up approximating the number of solutions (we relax the accuracy of the ...
0
votes
1answer
63 views

Proof of P ⊆ NP [duplicate]

What is the proof of P ⊆ NP? I cannot happen to find a good explanation for it. I read that the verifier will just ignore the proof and accept any proof if the ...
2
votes
1answer
36 views

Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
3
votes
1answer
49 views

Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ? I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ ...
2
votes
1answer
41 views

Polynomial space complexity with exponential size witnesses

Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has: Input tape: Read only, move in both directions. Witness tape: Read only, move only in one ...
0
votes
0answers
10 views

Show polynomial hierarchy levels closed under reduction [duplicate]

Most books assume that this is obvious, but I can't see how each $\Sigma_k=NP^{\Sigma_{k-1}}$ level in the polynomial hierarchy is closed under polynomial-time reductions. Is there something that I'm ...
-1
votes
2answers
39 views

Is it possible for an NP problem to be reduced to an EXPTIME problem in polynomial time?

And if so would this grant us any insight into the relations between P, NP, and EXPTIME?
0
votes
1answer
52 views

Does $DTIME(2^n)$ contain $NSPACE(n)$ ? [closed]

As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?
5
votes
2answers
103 views

Is DSPACE properly contained in NSPACE?

It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$? In other words, is the containment relation ...
4
votes
1answer
190 views

Are there any problems in complexity class EXP that are not in NP?

I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.
0
votes
1answer
46 views

Complexity of Double-Horn-SAT?

On one hand, Horn-SAT is known to be tractable in linear time - where Horn-SAT is the problem of deciding whether a given set of propositional Horn clauses (with at most one positive literal) is ...
2
votes
1answer
51 views

Is SAT is in NL?( under certain conditions)

Consider a certicate for 3SAT that lists an assignment for each occurrence of a variable in the order of appearence,e.g. 100000 for ($x\bigvee$$y\bigvee$z)$\bigwedge$($\neg(w)$$\bigvee$$y\bigvee$z). ...
3
votes
2answers
120 views

Problems in NP but not in #P

Are there problems that are in NP class but not in #P class? According to Wiki definition: More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number ...
7
votes
1answer
191 views

Complexity of (SAT to 3-SAT) Problem?

It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible ...
7
votes
1answer
133 views

Complexity of Monotone (+,2) SAT problem?

To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem: Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF ...
1
vote
1answer
70 views

NP-COMPLETE:Why say “reduction algorithm computes reduction function”?

In Chap 34.3 NP-completeness and reducibility of the book, Introduction to Algorithm(3rd Edition), the author states(the original text): We call the function f the reduction function, and a ...
3
votes
1answer
91 views

Are there problems that are polynomial-time equivalent to factoring composites?

It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = ...
11
votes
1answer
188 views

Complexity of deciding if a formula has exactly 1 satisfying assignment

The decision problem Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment? can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything ...
1
vote
0answers
36 views

Problems unsolvable by an oracle machine? [duplicate]

Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems? Even the Omega number, at least the first N digits, ...
4
votes
1answer
112 views

$\mathbf{NC}$ is closed under logspace reductions

I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a ...
2
votes
1answer
55 views

BPP upper bound

does $BPP\subseteq P^{NP}$ ? it seems reasonable but I don't know if there is a proof of this!could any one post a proof or any material that discusses the statement or something that look like this . ...
2
votes
1answer
72 views

What does $A^B$ mean?

What does $A^B$ mean where A and B are complexity classes? The "Polynomial Hierarchy" page says: $A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle ...
5
votes
0answers
64 views

'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game: Intance of 'Stones' game is: finite set $X$ relation $R \subseteq X^3$ set $Y \subseteq X$ and ...
3
votes
1answer
105 views

Is np-complete an equivalence class?

So, there are multiple possible definitions of "np-complete", two of which being: A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' ...
4
votes
1answer
101 views

Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?

let $L_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT_c=NP$. Assuming know that $NP\neq P$ we know that there exist languages ...
1
vote
1answer
910 views

Proving that if coNP $\neq$ NP then P $\neq$ NP

I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it. Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$. Show ...
4
votes
1answer
79 views

$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?

It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$. My question is whether the converse is true: is ...
1
vote
0answers
45 views

how to prove this unsolvable problem about halting problem (turing machine) [duplicate]

Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
3
votes
1answer
104 views

Are there any problems in $APX - PTAS$ that are not $APX$-complete?

I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the ...
2
votes
2answers
424 views

A Problem on Time Complexity of Algorithms

For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time? By verifying, I mean that given a candidate solution $y$, we can ...
2
votes
2answers
130 views

Is the problem of evaluating a boolean formula on a given assignment P-complete?

I know that the CIRCUIT VALUE problem is P-complete. In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given ...
2
votes
3answers
1k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
7
votes
2answers
107 views

Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
3
votes
2answers
147 views

How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?

I'm having a hard time understanding the actual proof of this proposition: $\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$ The sketch of the proof is on slides 6-8 ...
2
votes
2answers
127 views

Why does a polynomial-time language have a polynomial-sized circuit?

I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs ...
3
votes
1answer
105 views

Accurate definition of BPP

I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a ...
3
votes
1answer
407 views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...