Questions tagged [complexity-classes]

Computational complexity classes and their relations

-2
votes
1answer
118 views

Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...
2
votes
0answers
56 views

$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following: $FPT = XPuniform\implies EPTAS = PTAS$. Fundamentals of Parametrized complexity on page $534$ has ...
2
votes
0answers
132 views

Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
-1
votes
1answer
80 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?
17
votes
4answers
2k views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
6
votes
1answer
150 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
161 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 ...
5
votes
1answer
334 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 ...
37
votes
7answers
6k views

What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
9
votes
1answer
486 views

2-NEXPTIME-complete problems

We have a problem and we found an algorithm that appear to be 2-nexptime. I would like to find known 2-nexptime-complete problems in order to find a lower bound. I found in literature mainly two ...
1
vote
0answers
113 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
104 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
176 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
103 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, ...
6
votes
1answer
229 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
83 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 ...
6
votes
2answers
773 views

Isn't it trivial to represent any classical physics problem in a Spin-Glass language which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
9
votes
1answer
161 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
440 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, $\...
3
votes
0answers
127 views

Random self reducibility and NP

I was reading the Wikipedia page Random self-reducibility and it states: If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$. I am ...
36
votes
3answers
5k views

P and NP classes explanation through lambda-calculus

In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of ...
10
votes
1answer
373 views

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

If we can prove that $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ? I thought it is the case, but I cannot prove it (also for the converse).
0
votes
3answers
173 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: ...
-7
votes
2answers
572 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
1
vote
0answers
327 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^{...
8
votes
1answer
198 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 ...
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
69 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
254 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 ...
2
votes
1answer
111 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.
6
votes
1answer
177 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 ...
2
votes
1answer
253 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
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 ...
10
votes
1answer
364 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 ...
8
votes
1answer
171 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 ...
13
votes
1answer
381 views

Problems in NC not known to lie in NC2

Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
3
votes
2answers
407 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
119 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
188 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
1answer
380 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 ...
5
votes
1answer
292 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 ...
233
votes
11answers
115k views

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...
3
votes
1answer
235 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 ...
4
votes
1answer
236 views

Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
10
votes
1answer
258 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 ...
11
votes
1answer
318 views

Ruzzo-Simon-Tompa oracle access mechanism

In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some more pathological examples in this vein in ...
4
votes
1answer
109 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 ...
5
votes
1answer
349 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 ...
2
votes
0answers
190 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 &...