Questions about relationships between complexity classes.

learn more… | top users | synonyms

0
votes
0answers
11 views

$k$-query oracle Turing machine (Sipser 9.21)

Question: A $k$-query oracle Turing machine is an oracle Turing machine that is permitted to make at most $k$ queries on each input. A $k$-query oracle Turing machine $M$ with an oracle for $A$ is ...
1
vote
0answers
18 views

Proving $CVal$ is $RP$-hard

Let CVal be the language of all $<C,s>$ where $s$ is an $n-$tuple of binary values ($\{0,1\}$), such that $C$ is a variable-free boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and ...
4
votes
1answer
153 views

What's the meaning of the name P/poly?

I understand the normal definitions of the P/poly class, but I'm curious how the name came about. The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly ...
2
votes
1answer
35 views

Definition of $D^P$?

What is the definition of the complexity class $D^P$? In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too. Is it the ...
2
votes
0answers
25 views

crypto protocols from complexity class

Assume $P=PSPACE$. Then would it be possible to design cryptographic protocols based that is easy to compute from $PSPACE$ but hard to invert from something higher up in hierarchy? A function $f: ...
2
votes
1answer
98 views

Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$? If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above ...
0
votes
1answer
54 views

Which complexity class $3^{n/3}$

Assuming a problem has complexity $O(3^{n/3})$, Which is its class of complexity ? Despite that it is not as $2^{n}$ ,we can say is an exponential ?
6
votes
2answers
83 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
14
votes
2answers
1k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
1
vote
2answers
60 views

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

I'm so bad at solving the problem of the type "If A is an NP complete problem, B is reducible to A, then B is..." that I have to come here and ask these silly questions each and every time I encounter ...
2
votes
1answer
51 views

If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
6
votes
2answers
89 views

Analog of PP for computability rather than complexity?

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the ...
3
votes
1answer
57 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k ...
3
votes
1answer
114 views

Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ? Form what I understand: (easy things are the things that can be done in polynomial ...
3
votes
2answers
235 views

Decision problem which belongs to P reduced to a decision problem which belongs to NP?

Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?
0
votes
1answer
76 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
2
votes
1answer
84 views

Are there any coP problems

Is there a notion of coP problem? Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
0
votes
1answer
70 views

If P = NP, then is NP = FNP?

I read FP = FNP iff P = NP which makes sense. But if P = NP, does it mean FNP = NP? Intuitively, I think no because P = NP would mean that decision problems in NP would become decision ...
1
vote
1answer
64 views

Complexity of variation of partition problem

I want to know whats the complexity of the following variant of the partition problem: Partition problem: http://en.wikipedia.org/wiki/Partition_problem Suppose we have one set formed by integers ...
0
votes
0answers
27 views

Canadian traveller problem on directed acyclic graphs

What is the complexity of the Canadian traveller problem variant where the only thing that is seen is a single node ahead on a directed acyclic graph so that we cant go back once we go to a new node ...
7
votes
0answers
53 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
4
votes
1answer
52 views

Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input. The class $\Sigma^p_2$ contains all ...
8
votes
2answers
201 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
11
votes
2answers
107 views

Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
2
votes
1answer
74 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
70 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
95 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 ...
9
votes
1answer
85 views

What do complexity classes look like, if we use Turing reductions?

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this: (under standard conjectures). I'm sure we're all ...
3
votes
1answer
84 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
139 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
156 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
810 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
108 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
65 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
34 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
64 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
70 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
114 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
72 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
47 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
53 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
53 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
45 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
58 views

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

As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?
5
votes
2answers
125 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 ...
6
votes
0answers
92 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
4
votes
1answer
326 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
48 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 ...