Questions about relationships between complexity classes.

learn more… | top users | synonyms

2
votes
1answer
97 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
25 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
54 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
33 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
45 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
34 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
34 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
49 views

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

As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?
5
votes
2answers
94 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
128 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
37 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
41 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). ...
-2
votes
1answer
68 views

Proving $PH = NP$ [closed]

Show that if 3SAT is polynomial-time reducible to $complement of 3SAT$ then $PH = NP$. Above problem is Exercise problem from Arora and Barak, i don't know how to solve this problem,if anybody knows ...
3
votes
2answers
118 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
181 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
121 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
63 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
78 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
171 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
35 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
102 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
54 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
70 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 ...
4
votes
0answers
53 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
87 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
100 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
668 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
71 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
44 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
92 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
395 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
88 views

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

I know that the CVAL problem is P-complete. In the CVAL problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the ...
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
105 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
127 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
114 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
92 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
332 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 ...
2
votes
2answers
114 views

How to Prove E $\subsetneq$ EXP?

I want to prove that $E \subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof: $E\subseteq ...
3
votes
0answers
69 views

PARITY using depth one TC0 circuit

I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
2
votes
1answer
134 views

How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? [duplicate]

If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$: How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as ...
0
votes
2answers
82 views

Show complement of language in same complexity class?

If $L$ is a binary language ($\Sigma = (0, 1)^*$) and $\overline{L}$ is the complement of $L$, the set of binary strings not in $L$. How can I show that, if $L$ is in the complexity class $P$, then ...
2
votes
2answers
156 views

The exact relation between complexity classes and algorithm complexities [duplicate]

Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ? Are all algorithms which have non ...
2
votes
2answers
156 views

Is the open question NP=co-NP the same as P=NP?

I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem... ...
3
votes
2answers
292 views

Can we make a problem harder than NP and coNP if they are not equal?

Let us assume that $\mathsf{NP} \neq \mathsf{coNP}$. Consider the graph 3-colorability problem. Since $\mathsf{NP} \neq \mathsf{coNP}$ implies $\mathsf{P} \neq \mathsf{NP}$ and 3-coloribility is ...
10
votes
3answers
326 views

P, NP and specialised Turing Machines

I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the ...
3
votes
1answer
197 views

If NP $\neq$ Co-NP then is P $\neq$ NP

Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?
4
votes
3answers
234 views

Concrete understanding of difference between PP and BPP definitions

I am confused about how PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions ...
7
votes
3answers
591 views

Does P != NP imply that | NP | > | P |?

Is it possible that P != NP and the cardinality of P is the same as the cardinality of NP? Or does P != NP mean that P and NP must have different cardinalities?