Questions about relationships between complexity classes.
0
votes
1answer
48 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 ...
1
vote
0answers
42 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
25 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
3answers
219 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
33 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
2answers
222 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 ...
6
votes
2answers
63 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
78 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
55 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 ...
2
votes
1answer
52 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
141 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
72 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
51 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
78 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
64 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
71 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
97 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
155 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 ...
8
votes
3answers
140 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
172 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 ?
3
votes
3answers
114 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 ...
4
votes
2answers
270 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?
2
votes
2answers
62 views
Implications of polynomial time reductions
I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong.
I'm presented with a problem ...
5
votes
1answer
480 views
Is the k-clique problem NP-complete?
In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:
Cliques have also been ...
0
votes
1answer
54 views
coNP and limitation of NDTM
I try to understand if someone can apply a NTM to recognize coNP language.
From the definition we know that:
NP - set of languages that can be recognized by NTM in polynomial time.
coNP - set of ...
8
votes
3answers
248 views
Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$
I'd really like your help with proving the following.
If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.
Here, $\mathrm{NTime}(n^{100})$ is the class of ...
3
votes
1answer
90 views
Relation between interactive proof systems (IP), NP, coNP, PSPACE
I would like to ask you some clarification on the following question:
know that ${\sf NP}$ is a subset of ${\sf IP}$
and also ${\sf coNP}$ it is a subset of ${\sf IP}$.
So ${\sf IP}$ is a biggest ...
3
votes
1answer
138 views
Intuition behind Relativization
I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will ...
1
vote
1answer
151 views
Polynomial time reducibility
$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$.
$L_1$ is reducible to $L_2$ in polynomial time. Which of the following
cannot be true?
$L_1 \in P$ and $L_2$ is finite
...
8
votes
2answers
148 views
Some questions on parallel computing and the class NC
I have a number of related questions about these two topics.
First, most complexity texts only gloss over the class $\mathbb{NC}$. Is there a good resource that covers the research more in depth? ...
2
votes
0answers
116 views
Hardness of counting solutions to NP-Complete problems, assuming a type of reduction
The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
6
votes
1answer
205 views
Types of reductions and associated definitions of hardness
Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
3
votes
1answer
56 views
What is known about coRL and RL?
Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.
Are they the same class?
What are ...
6
votes
3answers
387 views
Generalised 3SUM (k-SUM) problem?
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.
It is conjectured that there is not better solution than quadratic, i.e. ...
7
votes
1answer
226 views
What is complexity class $\oplus P^{\oplus P}$
What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing ...
