Computational complexity classes and their relations
-3
votes
0answers
28 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' ...
3
votes
0answers
151 views
The number of maximal subsets with sum less than $m$
I've met this problem.
I would like to know to which complexity class it belongs.
Input
a set of positive integers $I$,
an integer $m$,
an integer $n$.
Question
Is the number of $S \subseteq I$ ...
-4
votes
0answers
41 views
CoNp!=NP then P!=NP [migrated]
I am new here, and new in theory of complexity in general, this question is a part of a homework that I have got and I was stuck on it, does anyone has the answer? I need it to prepare for the exam.
...
3
votes
0answers
100 views
$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$? [migrated]
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 ...
3
votes
1answer
188 views
Is the D-Wave architecture a close implementation of quantum interactive proof?
A very high level architecture is, as mentioned here, shown in this picture.
The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is ...
-3
votes
0answers
31 views
how to prove this unsolvable problem about halting problem (turing machine) [migrated]
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
106 views
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf ...
8
votes
0answers
159 views
Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?
(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
4
votes
1answer
203 views
On the proof of Meyer's Theorem
Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} ...
4
votes
0answers
80 views
Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits
Beigel and Tarui's transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the ...
6
votes
1answer
145 views
Consequences of OWFs for Complexity
It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
1
vote
0answers
68 views
Conditional Results on Bounded Depth Circuit Hierarchy
$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.
$AC$-hierarchy is $\bigcup _{i =0}^{\infty} AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of ...
-3
votes
0answers
89 views
TQBF $\notin$ SPACE($n^{1/3}$) [closed]
I want to show that TQBF $\notin$ SPACE($n^{1/3}$). Can I use the fact that TQBF is PSPACE-complete to show that there is a language L $\in$ SPACE(n) that reduces to TQBF in polynomial time, and ...
10
votes
0answers
263 views
What is the complexity of this edge coloring problem?
Recently, I have encountered the following variant of edge coloring.
Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
8
votes
3answers
359 views
What is the fastest known simulation of BPP using Las Vegas algorithms?
$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.
$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
3
votes
1answer
149 views
How powerful are nondeterministic constant-depth circuits?
A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow ...
11
votes
2answers
196 views
Is Parity-P contained in PP?
This question was asked by Jan Pax on the Foundations of Mathematics mailing list.
Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$
but I suspect from the answers to this question that it's not ...
12
votes
1answer
521 views
How can a problem be in NP, be NP-hard and not NP-complete?
For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.
However, in the famous paper "The ellipsoid method and its consequences in ...
7
votes
2answers
390 views
Is adiabatic quantum computing as powerful as qubit computing?
Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following.
Is adiabatic quantum ...
14
votes
1answer
191 views
Smooth Complexity of the Nonnegative Permanent
There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative ...
8
votes
1answer
820 views
About Inverse 3-SAT
Context: Kavvadias and Sideri have shown that the Inverse 3-SAT problem is coNP Complete:
Given $\phi$ a set of models on $n$ variables, is there a 3-CNF formula such that $\phi$ is its exact set of ...
7
votes
1answer
183 views
On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$
We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, ...
4
votes
2answers
442 views
P vs NP: Instructive example of when Brute Force search can be avoided
To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
5
votes
0answers
128 views
Big O notation for “modulo a polynomial”
Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition:
$f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$?
...
0
votes
0answers
46 views
Nonmetric TSP and Functional Compleixty Classes
Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.
Is this general TSP a complete problem in some functional complexity classes ?
...
0
votes
0answers
95 views
Smallest Nonuniform Complexity Classes including uniform-P
As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial.
For example, P/poly is defined as challenges to derive a separation between P and NP, because ...
2
votes
1answer
189 views
How do you argue a query is impossible in a query language like SPARQL or SQL?
I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For ...
4
votes
1answer
204 views
Computational Complexity of Computer Vision Problems
What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?
In most cases this will boil down to determining ...
7
votes
1answer
309 views
Does every Turing-recognizable undecidable language have a NP-complete subset?
Does every Turing-recognizable undecidable language have a NP-complete subset?
The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
1
vote
0answers
92 views
Structural equivalence of two context-free grammars
I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free ...
11
votes
1answer
409 views
Consensus on P = NP in a world where RP = NP
$RP = NP$ is widely conjectured to be false.
But imagine for a moment that it is true. In such case, how likely would be that $P = NP$?
Put in other words: in a world where $RP = NP$, what might ...
3
votes
0answers
115 views
Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER
The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph.
Question
Which is the ...
4
votes
1answer
244 views
How hard is to compute $\Delta_{|V|}$?
Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:
$$
|\mathcal{C}| = 2^{|V|} - \sum_{k = ...
8
votes
1answer
184 views
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
23
votes
3answers
539 views
Constructivity in Natural Proof and Geometric Complexity
Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.
Constructivity in Natural ...
0
votes
0answers
86 views
Fullness of regular expressions with exponentiation
Meyer & Stockmeyer proved many years ago that the following problem is NEXPSPACE complete, called "fullness of regular expressions":
Input: regular expression with exponentiation
Output: true if ...
2
votes
1answer
54 views
Natural relativized worlds
The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques ...
-2
votes
1answer
268 views
Computational complexities in factoring
[Note: n is a given integer (not the number of its digits)]
I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the ...
24
votes
3answers
600 views
Is NPI contained in P/poly?
It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then ...
7
votes
1answer
113 views
Complexity results for Lower-Elementary Recursive Functions?
Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.
The elementary recursive functions ...
6
votes
0answers
157 views
Narrowing the gap between BPP and RP
We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
5
votes
1answer
104 views
Complexity of Hidden Subgroup problems
Has anyone classified the (non-quantum) complexity of the hidden subgroup problem for finite Abelian groups? Is it known to be in any classical (not quantum) complexity classes?
8
votes
1answer
113 views
Algebraic (or numeric) invariants of complexity classes
I hope this question isn't too naive for this site.
In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical ...
6
votes
2answers
323 views
What is $DTIME(n^a)^{DTIME(n^b)}$?
This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where?
Update: There are three possible ways to ...
4
votes
1answer
139 views
Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?
${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there ...
1
vote
1answer
77 views
Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$
I'm reading a paper which shows the result:
$(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$
$(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$.
Both $(1)$ and ...
27
votes
0answers
481 views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = ...
0
votes
1answer
215 views
Counting reduction from #SAT to #HornSAT?
Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by ...
5
votes
1answer
320 views
What if a problem is both in $\Pi_2^p$ and $NP$-hard?
If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete?
If the answer is no, ...
7
votes
1answer
106 views
Literature for restrictions that make NPC-Problems to P
The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, it is in $\mathcal{P}$.
I've already heard similar statements. Do you know a more general statement when ...
