Questions tagged [complexity-classes]
Computational complexity classes and their relations
0
votes
0answers
41 views
How could the No Free Lunch Theorem be applied to complexity classes
I was reading a chapter from a book, which states: (section 11.3.4)
No Free Lunch (NFL) has not been proven to hold over the set of problems in the complexity class NP.
I was confused because NP ...
-4
votes
0answers
21 views
Prove that language in L
How to prove that $L = \{(\phi,x) | \space Boolean \space formula \space \phi \space is \space true \space on \space a \space set \space of \space x\} $ lies in L?
12
votes
1answer
347 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, $\...
-4
votes
0answers
74 views
Prove that if A is NP-complete and B is coNP-complete, than AxB is NP-, coNP-complete
AxB means cartesian product of A and B.
May someone help me with this? I even have no idea how to prove that AxB belongs to NP or coNP
0
votes
3answers
153 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
208 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
59 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 ...
11
votes
1answer
235 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
159 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
321 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 ...
1
vote
1answer
235 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. ...
7
votes
1answer
154 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
338 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
397 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
112 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 $...
5
votes
1answer
177 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}/\...
0
votes
0answers
61 views
Proving that a problem is coNP-complete [duplicate]
Let $\le^{p}_{T}$ be the Turing or the Cook reduction and $\le_{m}^{p}$ the Karp-Levin reduction.
I know that to prove a problem $P_1$ is coNP-complete I just need to show that $P_1 \in coNP$ and ...
4
votes
1answer
286 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
203 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
416 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
244 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
82 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
227 views
Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
5
votes
1answer
326 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
187 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
147 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
89 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
208 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
88 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.
2
votes
0answers
177 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
186 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
84 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
49 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
114 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
90 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 ...
2
votes
1answer
122 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
120 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
276 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
100 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
36 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
470 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
208 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 ...
7
votes
4answers
265 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 ...
0
votes
1answer
322 views
What are the problems in EXPSPACE \ EXPTIME?
Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial ...
0
votes
1answer
72 views
Reduction from SAT to binary matrix subset problem
I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new ...
1
vote
2answers
190 views
If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?
NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.
Is there a ...
5
votes
0answers
165 views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
11
votes
1answer
450 views
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
1
vote
1answer
72 views
PromiseBQP and expectation values of operators
This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,
... a difficult and unsolved meta-question is whether PromiseBPP = ...
