Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
324
questions
4
votes
1answer
61 views
Is DISCRETE LOG a NP hard problem?
In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:
FACT ...
0
votes
0answers
34 views
If P = NP then EXPTIME = NEXPTIME?
Are the following implications correct?
If P = NP then EXPTIME = NEXPTIME
If P $\neq$ NP then NEXPTIME = 2EXPTIME
If so would the corresponding implications hold for N2EXPTIME, etc.?
2
votes
2answers
44 views
Big-O Notation and Calculus?
I was wondering if there are any calculus relationships implicit in Big-O notation.
For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
1
vote
1answer
63 views
Does EXP^EXP = EXP? [duplicate]
Does $\mathrm{EXP}^\mathrm{EXP}=\mathrm{EXP}$?
Here is my thought: $\mathrm{EXP}$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a ...
1
vote
0answers
17 views
Which is harder, an NP-complete problem or the Raz-Tal oracle problem?
This is a (hopefully) sharper version of a question that I asked previously.
Which of these algorithms is believed to have a longer asymptotic runtime?
The optimal algorithm guaranteed to solve some ...
1
vote
0answers
14 views
Do relativized relations between complexity classes tell us anything about the nonrelativized relation?
The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the ...
0
votes
1answer
46 views
Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem
We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:
Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...
1
vote
1answer
35 views
Complexity of K-Colorful Coloring Problem for a Hypergraph
I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
0
votes
0answers
14 views
$P$ with $SAT[k]$ and $NP[k]$ oracles?
We know $coNP$ is in $P^{NP}$ and so does $coNP$ in $P^{NP[1]}$ and $P^{SAT[1]}$ hold?
Is there a difference between $P^{SAT[k]}$ and $P^{NP[k]}$ at any $k\geq0$?
0
votes
0answers
43 views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
0
votes
1answer
43 views
prove that there is a complete language in $L \cup \{A_{TM}\}$
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$
$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space
Given the language $L ...
2
votes
0answers
33 views
Is PSPACE vs NEXPTIME known?
I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME.
Is anything known about ...
1
vote
1answer
22 views
Problem class of assigning N persons to N tasks, zero costs with prefs
I am looking for the general problem class / computational complexity / algorithms for the following problem:
N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice ...
1
vote
2answers
19 views
Why do we use worse-case when categorising problems?
Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.
Why don't we use the average case?
I imagine we could have a problem ...
1
vote
2answers
72 views
DSPACE(f(n)) closed under complement
I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
0
votes
1answer
122 views
Proving NP completeness of maximal length path
I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
2
votes
1answer
26 views
NL-Hardness of Target
When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:
$ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
0
votes
1answer
34 views
A simple clarification on polynomial hierarchy
$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true?
$P^{\Sigma_2^P\cup\Pi_2^P}\subseteq ...
0
votes
0answers
18 views
Why is $BPP^{NP}$ in the polynomial hierarchy?
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine ...
0
votes
0answers
30 views
is this given language in class P? [duplicate]
i was wondering:
is this language in class P?
$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$
explanation: a ...
0
votes
1answer
27 views
Can CNF with an input string be evaluated in logarithmic space?
I have been trying to solve satisfiability of
{$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}.
As first looks to me, it is satisiable in linear time ($O(n)$) since ...
2
votes
1answer
35 views
On the robustness of BQP class
Typically the notion of quantum Turing machine is introduced with its transition function.
$$
\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}
$$
Where $\mathbb{C}'\...
1
vote
1answer
24 views
Changing probabilities to 0/1 in definition of class IP
A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$,
$$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\notin L\Rightarrow Pr[V\...
3
votes
1answer
70 views
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
0
votes
0answers
37 views
Reduction of complement from complexity class co-np and p
Let P $ \neq $ NP.
D is in the complexity class co-NP.
B is in the complexity class P.
Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B.
Is this statement true or false? My ...
1
vote
1answer
29 views
Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$
I've been struggling for a while trying to solve this problem:
Show that the following problem is in $\mathbf{NP}$:
Check that a system of linear equations with $m$ integer variables and
integer ...
1
vote
1answer
43 views
Proof of proposition between Precise Turing Machine and Proper Complexity function
In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim.
Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, ...
1
vote
2answers
35 views
NP-hardness does not imply lower bound, strictly speaking?
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.
Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
1
vote
0answers
8 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?
1
vote
1answer
11 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
16 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
47 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
21 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
32 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
23 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
48 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
225 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
168 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 ...
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
19 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
108 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
25 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
110 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
votes
1answer
30 views
Complexity classes that are low for equivalent definitions of $\mathrm{PP}$
What is the biggest complexity class that is low for each other equivalent definition of $\mathrm{PP}$?
I already know that $\mathrm{PP}^\mathrm{BQP}=\mathrm{PP}$. This is a lowness result using ...
1
vote
1answer
59 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
28 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
26 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 ...
3
votes
1answer
103 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
40 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 ...
