Computational complexity classes and their relations
0
votes
0answers
2 views
how to prove this unsolvable problem about halting problem (turing machine)
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
89 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
120 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
166 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
79 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
138 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
64 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 ...
9
votes
0answers
228 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 ...
-1
votes
0answers
29 views
Are all Integer Linear Programming problems NP-Hard? [migrated]
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 ...
8
votes
3answers
357 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
146 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
192 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 ...
11
votes
1answer
511 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
387 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
809 views
+50
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
181 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
435 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
93 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
200 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
304 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
358 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 ...
2
votes
0answers
113 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
243 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
84 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
262 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
598 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
155 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
110 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
138 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
76 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
478 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
212 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 ...
-5
votes
1answer
176 views
Is 3SAT problem APX-hard or not?
Could you point me a reference, an answer or it is an open question?
6
votes
0answers
98 views
The power of randomized logspace with two-way access to the random tape
Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the ...
5
votes
1answer
103 views
Two way deterministic multihead counter automata or logspace TM with counter
Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. ...
12
votes
0answers
155 views
Descriptive complexity characterization of TimeSpace classes
Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
