Questions tagged [complexity-classes]
Computational complexity classes and their relations
-1
votes
1answer
78 views
Why is $BPP^{NP}$ in polynomial hierarchy? [closed]
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. However, how does that imply $BPP^{NP}$ is inside the polynomial hierarchy?
6
votes
1answer
142 views
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
3
votes
1answer
151 views
String theory based computations
I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
0
votes
0answers
108 views
Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$
Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
8
votes
0answers
98 views
Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?
Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.
However, if we consider larger complexity classes such as ...
11
votes
0answers
175 views
Computational Complexity of the Frobenius Problem
The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
1
vote
2answers
102 views
When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]
In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
7
votes
1answer
226 views
Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)
In the wikipedia article on Time Complexity it is written that:
The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
-3
votes
1answer
82 views
Are there any known languages in the intersection of NP and co-NP but not in P? [closed]
We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in ...
10
votes
1answer
160 views
Natural candidates for NP-E and E-NP
It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
14
votes
0answers
435 views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
0
votes
3answers
170 views
Hamiltonian cycle vs co-NP [closed]
I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
...
1
vote
0answers
270 views
EXPSPACE proof and its implications
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.
\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n ...
1
vote
0answers
68 views
Complexity of enumerating over promise problems and circuits?
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
12
votes
1answer
250 views
Is DSPACE(n) = DSPACE(1.5n)?
From space-hierarchy theorem it is known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.
Here, by DSPACE($f(n))$ I mean the class of all problems that can ...
6
votes
1answer
174 views
Does Max Planar 3-SAT admit a PTAS?
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
7
votes
1answer
330 views
“Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?
Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
3
votes
1answer
251 views
$P=BPP$ without good PRGs?
We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.
Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. ...
8
votes
1answer
168 views
Type theory and computational complexity
Is there a type system, which restricts the lambda terms to the terms which fall inside a complexity class? Like the typable terms in the theory are strictly inside the complexity class ? Or is it not ...
10
votes
1answer
362 views
What is the complexity of this game?
This is a generalization of my previous question.
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
3
votes
2answers
405 views
Is there a non-deterministic version of the complexity class PP?
From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)
Edit: Perhaps I ...
8
votes
0answers
117 views
Complexity of fractional SAT
Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
6
votes
1answer
187 views
Boolean circuits which correspond to L/poly
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
5
votes
1answer
332 views
Indications that strengthen the conjecture: NEXP ⊊ EXP^NP
I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.
Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.
Some Examples:
1. A paper by Shuichi ...
3
votes
1answer
227 views
Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$
Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ has any separation of classes or consequences?
My main question is can use this to show that $P \neq NP$ or some thing useful ...
16
votes
0answers
422 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
10
votes
1answer
257 views
Is this game EXPSPACE-complete?
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be ...
4
votes
1answer
104 views
Complexity of type-checking in relation to complexity of normalization
In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can ...
4
votes
1answer
236 views
Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
5
votes
1answer
345 views
Can one do quantum computing without negative amplitudes?
The typical representation I see of $k$ qubits is a $2^k$ complex numbers $c_i$ for every possible combination of values of those bits, such that the sum of all the squared magnitudes of those numbers ...
8
votes
1answer
193 views
How “hard” is it to maximize a polynomial function subject to linear constraints?
General Problem
Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
4
votes
1answer
156 views
How powerful is POSIX regex
The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the ...
1
vote
0answers
91 views
An explicit hard function for P/poly
It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$?
(An example ...
6
votes
1answer
234 views
What are the consequences of solving XOR 3-SAT in Logspace?
XOR Formulas
Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
2
votes
1answer
108 views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
1
vote
0answers
274 views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$?
In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
2
votes
0answers
188 views
Primality in $NC$ hierarchy?
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:
Input: integer n > 1.
Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
0
votes
1answer
94 views
Is Prime Bounded Quadratic Congruence NP-complete?
Bounded Quadratic Congruence:
Instance: Three positive integers $a$, $b$ and $c$.
Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?
Bounded Quadratic ...
1
vote
0answers
54 views
An alternative characterization of some NExp-Time Turing machine with oracles
Let me denote by $\Sigma_i^P$ be a class from i-th level of polynomial time hierarchy (see eg. PH).
I'm interested in the following type of a Turing Machine $\mathcal{M}$:
$\mathcal{M}$ is ...
1
vote
0answers
141 views
Is there any NC-complete problem with respect to logspace reduction?
The question is on the title.
We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
8
votes
1answer
92 views
$BPL$ with polylog random bits is in $L$
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.
My question is ...
3
votes
1answer
127 views
Best $\Pi_k \text{SAT}$ running time?
Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$,
where $\phi(y_1, \dots, y_k)$ is boolean predicate with ...
3
votes
0answers
126 views
What are the consequences if $W[i]=W[i-1]$?
$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
5
votes
1answer
289 views
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?
This question came up while watching "Graduate Complexity at CMU - Lecture 2: Hierarchy Theorems (Time, Space, and ...
1
vote
0answers
103 views
Proof of Sipser-Lautmann Theorem
I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
1
vote
0answers
37 views
Monotone complexity of PLP
Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
0
votes
1answer
74 views
Constrained Topological Sorting with bounded number of chains
In general, constrained topological sorting is NP-hard.
Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
3
votes
3answers
542 views
Why is the circuit class AC0 unavoidable?
Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?
My problem is that in the case of unbounded fan-in, AND and OR gates ...
1
vote
2answers
210 views
Efficiently computable by a “simple” algorithm?
I am interested in the relation between "program complexity" and "computational complexity".
In particular, I was wondering
What is known about the minimal length a program must have to solve a ...
8
votes
4answers
271 views
What are semantic classes that have a syntactic equivalent?
This question is related to Benefits for syntactic and semantic classes.
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a ...
