Questions tagged [complexity-classes]

Computational complexity classes and their relations

Filter by
Sorted by
Tagged with
3 votes
0 answers
76 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
1 vote
0 answers
173 views

Perm and Det mod $2^k$ - II

Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
3 votes
0 answers
60 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
0 votes
0 answers
54 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
4 votes
0 answers
142 views

Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
1 vote
0 answers
73 views

Are there any candidate languages in NE but not E?

Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$ Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
-1 votes
1 answer
134 views

Solve 3CNF in Poly-Time with Satisfiability Oracle

The problem: Given an algorithm A which can tell whether any 3CNF formula is satisfiable in poly-time, develop an algorithm B that calculates a solution for the formula, also in poly-time, using A as ...
4 votes
1 answer
153 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
5 votes
0 answers
263 views

What's wrong with this $P \neq BPP$ proof?

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is. By the Union Theorem, there exists a total ...
8 votes
1 answer
476 views

What can we do with a generic oracle (as opposed to a random one)?

Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question): Standard definitions: A ...
1 vote
0 answers
74 views

Crafting ${NP}^{\#P}$-complete problems

Some related posts: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$? $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$ I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
0 votes
0 answers
108 views

Assume `P != NP`, does it imply that one-way functions exist?

I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
2 votes
1 answer
291 views

Deciding finiteness of regular language is NL-complete?

I've been reading the following Habilitation thesis where the author claims (pg. 29): ... First, deciding whether the language of an NFA is finite is in NL ... I'm having trouble seeing why this ...
5 votes
1 answer
418 views

Relation between ACC^0 and DTIME

In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$. How far can we potentially push this result? In other words, what is the largest $...
1 vote
0 answers
169 views

Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
3 votes
0 answers
116 views

Computational complexity of finding the $n$th Dedekind Number

Recently, two independent groups of researchers exactly calculated the $9$th Dedekind Number (see e.g. Quanta). The $n$th Dedekind Number counts the number of antichains consisting of subsets of $\{1,...
1 vote
1 answer
122 views

Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
5 votes
0 answers
131 views

Do fast satisfiability algorithms imply fast algorithms for parity SAT?

$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P). Suppose we have a ...
12 votes
2 answers
427 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 ...
10 votes
1 answer
829 views

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
1 vote
0 answers
86 views

What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...
7 votes
1 answer
298 views

Is there a well-defined notion of an “R/poly” complexity class?

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
6 votes
3 answers
361 views

Structural Complexity Theory References

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory. As an undergraduate, I completed an independent reading ...
1 vote
0 answers
165 views

How "Algebrization" is "A New Barrier in Complexity Theory"?

Being an enthusiast in computational complexity theory, I recently came across with this wonderful work Algebrization: A New Barrier in Complexity Theory. My question is about Theorem 5.3 in it (pp. ...
7 votes
0 answers
215 views

Relationships between Descriptive Complexity and Average Case Complexity

Descriptive complexity gives one a logic or at least a logic to express languages in a complexity class. The PH can be defined as the union of all classes that can be expressed in Second order logic. ...
3 votes
1 answer
192 views

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc. For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games: It is ...
2 votes
0 answers
45 views

Reducing the amount of alternations without exponentially increasing the runtime?

Let $\mathsf{AltTime}(g(n), f(n))$ denote the class of languages that are solvable by an alternating machine using $f(n)$ time and $g(n)$ alternations. Is there anything known about the following ...
3 votes
1 answer
257 views

Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
0 votes
0 answers
71 views

Are there any examples of problems in ZPP not yet in P? [duplicate]

Is there a problem of which we can prove that it is in ZPP but we don’t yet know whether it’s in P or not?
9 votes
1 answer
301 views

Complexity of permanent verification

Consider the problem of permanent verification: $\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$? Question: Is it known to be NP-hard? Should ...
10 votes
3 answers
502 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 ...
3 votes
0 answers
104 views

How do we show directly coNP is in MIP?

I know one can show that by $\mathsf{coNP}\subseteq\mathsf{NEXP}=\mathsf{MIP}$. But here I would like to start with a $\mathsf{coNP}$-complete problem and show there is a two-prover one-round ...
1 vote
1 answer
112 views

Explanation of Complexity class $S_2^P$?

I am trying to understand the complexity class $S_2^P$ defined as (https://en.wikipedia.org/wiki/S2P_(complexity)). A language L is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that:...
7 votes
0 answers
181 views

Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

Context I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
26 votes
3 answers
1k views

Optimization problems with minimax characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
3 votes
1 answer
228 views

Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
2 votes
0 answers
77 views

Variants of complexity classes that allow "adversarial inputs"?

Wikipedia defines BPP as follows: Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic ...
2 votes
1 answer
109 views

Complexity of computation of ANF-form (Zhegalkin polynomial)

Let $f: \mathbb{F}_2^n \to \mathbb{F}_2$ be a boolean function. Consider $f$ as a multilinear polynomial over $\mathbb{F}_2$ (algebraic normal form or Zhegalkin polynomial). How hard is to define the ...
10 votes
3 answers
2k views

Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
6 votes
0 answers
159 views

Consequences of $P^{NP[o(n)]} = P^{NP}$

I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$? I ...
2 votes
0 answers
42 views

Tape reduction, tape compression and time compression

In our lecture we have the following relationships: I have problems to understand these abstract classes. First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes. DSPACE(...
3 votes
0 answers
102 views

$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$

I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
0 votes
0 answers
147 views

On the use of Turing machines for computational complexity

Almost always in the study of computational complexity, the Turing machine is used as a model. On the other hand, the untyped lambda calculus is in a sense "simpler" than any Turing machine: ...
1 vote
0 answers
72 views

Is NLOGTIME self-low?

https://en.wikipedia.org/wiki/Low_(complexity) Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. EXP, which is closed ...
3 votes
1 answer
250 views

Relativized world in which P ≠ NP = coNP

Do we know of an oracle relative to which P ≠ NP but NP = coNP?
4 votes
0 answers
110 views

$\mathsf{NL}$ vs. $\mathsf{AC}^1$

It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$). Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
4 votes
2 answers
435 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 ...
5 votes
1 answer
127 views

DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

We know that $DET$ is in $VP$. And also from https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf I came to know that $DET$ is $VQP-complete$. Now certainly $VP\subseteq VQP$. That implies $...
44 votes
3 answers
7k 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 ...
0 votes
0 answers
100 views

Non-uniformity assumptions in circuit complexity

I recently came accross the following standard inclusion of complexity classes: $$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...

1
2 3 4 5
14