# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

349 questions
Filter by
Sorted by
Tagged with
549 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 ...
118 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 ...
428 views

149 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 ...
12k 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 ...
148 views

281 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 ...
2k 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 ...
356 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 ...
706 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 ...
13k 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...
1k views

648 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 ...
1k 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 ...
1k 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 ...
1k views

15k 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. $\mathcal{o}(n^2)$....
96 views

### Complexity class that properly included in DLOGTIME

Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course) If there is, can we create complete problems for DLOGTIME? So, can there be ...
### NP $\subsetneq$ EXP?
I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book ...
### 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 ...