Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
-3
votes
0answers
11 views
#P=NP: All satisfying solutions are valid answers by programs for NP
In fact, the implication looks like an equivalence too.
All satisfying solutions to a boolean formula
are valid answers by programs for NP
is equivalent to saying
the class #P equals the class NP.
...
1
vote
0answers
5 views
$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?
We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
0
votes
0answers
23 views
Proofs of the form “$A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}, \ A \not\leq_p B$”
I'm currently learning about complexity classes and I have a few general questions:
Assume $A, B \in \mathcal{NP}\setminus{\mathcal{P}}, \ A, B \not\in \mathcal{NP-C}$
are people generally ...
1
vote
1answer
10 views
Alternative formulation of complexity class $BPP$
In Aurora and Barak, they give the following alternative definition of $BPP$:
What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to ...
1
vote
0answers
12 views
Other problems in UP and co-UP
Are there any known problems in $UP \cap co-UP$ other than integer factorization and parity games (or a problem that can be reduced in polynomial time to either problem), that aren't known to be in $P$...
0
votes
1answer
46 views
Why all problems are not in P complexity?
İf Somebody wants to play perfect chess.I consider for finding solution to this problem,possible minimum data compression method which describes with 10 bit maximum possible data is in the range of 2^...
1
vote
0answers
19 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
0
votes
0answers
20 views
$\mathbb{NEXP\subseteq(NEXP\cap coNEXP)/poly}\implies \mathbb{NEXP=NEXP\cap coNEXP}$
We already know that $NEXP\subseteq EXP/poly\implies NEXP=EXP$. What if we change $EXP$ to $NEXP\cap coNEXP$.
As the title states, prove the statement in the title.
The original proof use the self-...
0
votes
1answer
16 views
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
2
votes
1answer
33 views
Relationship between complexity classes XP and W[1]?
I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.
...
4
votes
1answer
217 views
Is exponentiation in P?
I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?
Inputs: two numbers $(a,b) \in \mathbb{N}$
Output: $a^b$
0
votes
1answer
36 views
Will such an algorithm be feasible, will it be considered a poly time algorithm?
Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in the worst case,
$O(p\mathrm{log}(p))$,
will it be counted as a poly time algorithm ? Or ...
0
votes
1answer
86 views
Modular exponentiation running time
I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).
Is it poly ...
0
votes
0answers
14 views
On the class $\mathcal{BPP}$ (Bounded Probability Polynomial Time)
We say that language $L$ is recognized by the probabilistic polynomial time Turing machine $M$ if
for every $x\in L$ it holds that $P[M(x)=1]\ge\frac23$, and
for every $x\not\in L$ it holds that $P[M(...
1
vote
1answer
34 views
If a language is contained in other langauge, is it of the same complexity?
If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P?
Thanks :)
0
votes
1answer
15 views
$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$
Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.
For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.
1
vote
1answer
101 views
P=NP giving a deterministic algorithm for SAT
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying ...
1
vote
1answer
23 views
Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
2
votes
1answer
57 views
Show that RP is closed under concatenation
I'm trying to prove the following problem:
Show that $RP$ is closed under concatenation
Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
1
vote
1answer
56 views
Looking for a problem provably not in P
My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. ...
2
votes
1answer
25 views
Is there a complexity class “BQP without error”?
I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm ...
1
vote
0answers
22 views
What if $PSPACE$ falls to non-uniformity?
We know if every language in $EXP$ has polysize circuits, then $P\neq NP$ and $EXP=PSPACE=\Sigma_2^P\cap\Pi_2^P$.
If every language in $PSPACE$ has polysize circuits, then does it give anything (note ...
0
votes
0answers
28 views
Does floor and ceiling in LP implies more than $P=NP$?
We know ability to take floor and ceiling in Linear Programming (LP) implies $P=NP$ (just apply floor and ceiling to variable in $(0,2)$ to get binary variable and from this it follows $0/1$ ...
3
votes
1answer
79 views
Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$?
We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof.
Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\...
1
vote
1answer
34 views
Question on time hierarchy [closed]
How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?
(sorry about how it is written. I mean the set of languages decided by a deterministic ...
2
votes
0answers
24 views
Do undecidable problems have no HO query? If so, could I have an example?
In descriptive complexity, HO corresponds to ELEMENTARY.
ELEMENTARY is a subset of R, so therefore all HO queries are decidable.
Then undecidable problems have no corresponding HO query. Is my ...
0
votes
2answers
66 views
Defining decision-problem complexity classes by counting branches of a polynomial-time NTM
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
5
votes
1answer
84 views
Have any natural complexity classes been proven not to be closed under complement?
Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?
I'm sure one could construct some contrived ...
1
vote
1answer
87 views
Assumption: A PSPACE-hard problem can be solved in polynomial time
Under the assumption that a PSPACE-hard problem A can be solved in polynomial time, is the following argumentation valid?
Since every problem in PSPACE can be ...
0
votes
0answers
35 views
Decidability of language that contains all TM encodings that accept at least one word
I have a language that contains all encodings of the Turing machines that accept at least one word.
Is this language recursive, recursively enumerable, or neither?
3
votes
1answer
87 views
Is $NP\subseteq DTIME(2^{\theta(\sqrt n)})$ never possible?
$DTIME(2^{\sqrt n})$ is not closed under polynomial changes of $n$ however $DTIME(2^{polylog(n)})$ is.
So if $3SAT$ were in $DTIME(2^{polylog(n)})$ then $NP\subseteq DTIME(2^{polylog(n)})$ holds.
...
0
votes
0answers
47 views
$SAT$ and $BPP=P$ conjecture?
$BPP$ is the complexity class that accepts all languages for which there is Poly time TM with at least $1/3$ of their computation paths accept and rejects all languages for which there is Poly time TM ...
0
votes
2answers
59 views
From $P=NP$ to $NP=NL$
Does $P=NP$ implies $3SAT$ reduces to $2SAT$?
If so then from $2SAT$ is $NL$-complete can we conclude $NP=NL$?
2
votes
1answer
29 views
Is it known that $AC^1 \subseteq L$?
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
2
votes
1answer
75 views
Is every PSPACE-complete problem complete with respect to logspace reductions?
A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$,
$$
A \le_L ...
-1
votes
1answer
72 views
On NP and PP in RP?
Does $NP\subseteq RP\implies NP=RP$?
Does $PP\subseteq RP\implies \oplus P=NP=RP$?
At least what additional minimal conditions will give truth of above?
1
vote
1answer
24 views
Complexity for nested #P?
Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula ...
3
votes
2answers
77 views
Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?
This "research vignette" (whatever that is) claims that the polynomial hierarchy
classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of ...
2
votes
1answer
43 views
Comparison between MA and $P^{NP}$
I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma_2^{P}\cap \Pi_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi_{2}^{P}$.
My question is: In this whole thing, where does $P^{...
3
votes
1answer
86 views
Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?
It is within polynomial hierarchy so I assumed it is decidable. The picture like this further hinted in that direction.
Yet, in a paper on page 2 I read
Satisfiability of [...] is highly ...
0
votes
1answer
56 views
PSpace-completeness under PSpace reductions
A language $L$ is PSpace-complete, if it meets two conditions:
It is in PSpace.
Every other PSpace-complete language reduces to it in polynomial time.
Question: suppose we change the second ...
0
votes
1answer
36 views
$UP=BPP$ implies $UP=RP$?
https://cseweb.ucsd.edu/~mihir/cse200/ss6.pdf shows $NP$ in $BPP$ implies $NP$ in $RP$ by showing $SAT$ is in $RP$ if $NP$ is in $BPP$ and since $SAT$ is $NP$ complete we have $NP$ is in $RP$.
...
2
votes
1answer
64 views
Why doesn't this put $BPP$ in $NP$?
From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$
From Adleman we know $x\in L(M)...
0
votes
1answer
53 views
On clarification of intersection of classes definition
How do you define $\oplus P\cap PP$?
$L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$.
$L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$.
Consider ...
0
votes
1answer
46 views
$\#P$ closure under binomial coefficients? [closed]
It is quite straightforward to understand $\#P$ closure under addition and multiplication since there are canonical $NTM$ constructions.
Is there illustrative non-trivial example to understand $NTM$ ...
-1
votes
1answer
36 views
Why is $MOD_{p^k}P=MOD_pP$ at every prime $p$?
Complexity zoo states that $MOD_{2^k}P=MOD_2P$.
It is clear that if $MOD_2P$ accepts (number of accepting paths is off) then $MOD_{2^k}P$ accepts.
Why is it clear that if $MOD_2P$ rejects (number of ...
0
votes
2answers
46 views
A simple clarification on $\#P$ closure properties
What does $\#P$ closure under addition and multiplication mean?
Does it mean given $NTM$s $N_1$ and $N_2$ we can create in deterministic polynomial time an $NTM$ $N_\times$ and $N_+$ such that for ...
2
votes
1answer
36 views
Is there a name for this class?
The class $C_{1,\epsilon }$ of decision problems solvable by an NP machine such that
If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.
If the answer is 'no,' ...
3
votes
1answer
72 views
What is the consequence of $\oplus P\neq PP$?
From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that
$$P\neq PSPACE.$$
Are there any other consequences?
4
votes
1answer
54 views
Why not a $coNP$ hierarchy?
In the polynomial hierarchy we have $\Sigma_2=NP^{NP}$ and $\Pi_2=co\Sigma_2$.
So we have $\Pi_2=co(NP^{NP})$.
Is it same as $(coNP)^{NP}$?
I just wonder why not a hierarchy with $coNP$.
