Questions about relationships between complexity classes.

learn more… | top users | synonyms

4
votes
1answer
30 views

Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
1
vote
1answer
27 views

Prove that $coRP \subseteq RP^{RP}$

I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$. If $L \in coRP$, I don't understand how access to the oracle helps to build a ...
2
votes
1answer
60 views

Implications of $NP = \Sigma_2 P$ for PH collapse

A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement. I am having trouble seeing that an analogous statement is true at higher levels of ...
5
votes
2answers
141 views

Complexity of “given a graph $G$ with vertex $v$, is there a maximum clique containing $v$”?

The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard). Another ...
0
votes
1answer
66 views

Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?

If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply ...
2
votes
0answers
36 views

Relations between P^#P, NP^#P and (CO-NP)^#P

I was wondering if there were relation between the complexity classes $P^{\#P}$, $NP^{\#P}$, $(Co-NP)^{\#P}$ ?(except the trivial inclusions) I've the feeling that when taking a $NP^{\#P}$ machine, ...
4
votes
1answer
293 views

Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, ...
0
votes
0answers
42 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
3
votes
1answer
25 views

P/Poly class - undecidable lanauge

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| ...
4
votes
1answer
42 views

Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
1
vote
0answers
59 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
0
votes
0answers
26 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
2
votes
2answers
75 views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
1
vote
1answer
54 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
7
votes
0answers
39 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
3
votes
2answers
115 views

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his ...
2
votes
1answer
74 views

A particular complexity

Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?
3
votes
1answer
64 views

Is the minimal number of colors needed to color a graph some fixed number?

Consider to following decision problem: Input: Undirected graph $G=(V,E)$ Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices ...
2
votes
1answer
64 views

Proof of $P^{\text{#}P} = P^{PP}$

I was reading this article on the complexity class $PP$. In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please ...
5
votes
1answer
38 views

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then ...
1
vote
1answer
68 views

What's wrong here, or, is CNF to DNF conversion in o(exp(n))?

I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and ...
1
vote
1answer
62 views

Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) [duplicate]

I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble. Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of ...
0
votes
0answers
45 views

2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
3
votes
0answers
24 views

A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
1
vote
0answers
32 views

Status of $BQP^{NP},NP^{BQP}$

The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?
9
votes
1answer
82 views

Are there any natural $\Pi_2^P$-complete problems?

I know that the quantified Boolean formula problem for a formula $$ \psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi $$ where $\phi$ contains no quantifiers and only the ...
1
vote
1answer
95 views

PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
3
votes
1answer
110 views

What is the relation between NC and P/poly?

I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)
2
votes
0answers
189 views

PSPACE completeness, with different kinds of reductions [closed]

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
10
votes
1answer
125 views

Proof of Karp-Lipton theorem

I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009). In particular, this book states the following: ...
4
votes
1answer
49 views

What is an $NP^{NP}$-complete problem? [duplicate]

So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. ...
1
vote
1answer
53 views

FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?
2
votes
1answer
29 views

Can we separate P and E?

Let $\mathsf E$ be deterministic exponential time with linear exponent. Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict? If so, what's the proof? The time hierarchy ...
7
votes
1answer
191 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
3
votes
1answer
73 views

FP^NP-complete problems

Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?
2
votes
1answer
27 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
0
votes
0answers
32 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
31 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
190 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
38 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
29 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: ...
3
votes
1answer
108 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
60 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 ?
8
votes
3answers
175 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 ...
15
votes
2answers
2k 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
207 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 ...
2
votes
1answer
198 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
98 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
68 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
195 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 ...