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 ...
Marsh's user avatar
  • 31
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 ...
DiegoEmilio's user avatar
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 ...
apirogov's user avatar
  • 101
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 ...
108_mk's user avatar
  • 225
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 ...
Eleonora's user avatar
-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 ...
Dilara's user avatar
  • 1
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 ...
trillianhaze's user avatar
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 ...
rus9384's user avatar
  • 355
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 ...
Gro-Tsen's user avatar
  • 841
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 ...
Habri's user avatar
  • 11
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 ...
Zazaeil's user avatar
  • 212
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 ...
user avatar
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 $...
Nicholas Brandt's user avatar
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 ...
A. G's user avatar
  • 111
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,...
Clay Thomas's user avatar
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, ...
roignoirewg's user avatar
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 ...
Michael Lampis's user avatar
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. ...
Ilk's user avatar
  • 920
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 ...
Colonizor48's user avatar
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. ...
Souvik's user avatar
  • 19
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 ...
LiminalSpace's user avatar
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. ...
user3483902's user avatar
  • 1,261
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 ...
edit's user avatar
  • 33
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 ...
rus9384's user avatar
  • 355
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?
blademan9999's user avatar
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 ...
Igor Pak's user avatar
  • 812
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 ...
user50394's user avatar
  • 139
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:...
J.Doe's user avatar
  • 468
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 ...
Thiago's user avatar
  • 119
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 ...
Manuel Eberl's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Turbo's user avatar
  • 12.9k
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 ...
Jason Gross's user avatar
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 ...
Alexey Milovanov's user avatar
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 ...
user68775's user avatar
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(...
mathquester's user avatar
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 ...
Glycerius's user avatar
  • 131
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: ...
Wasabi Kurosawa's user avatar
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 ...
l4m2's user avatar
  • 111
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?
Noel Arteche's user avatar
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 $\...
Alexey Milovanov's user avatar
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 ...
Turbo's user avatar
  • 12.9k
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 $...
Soham Chatterjee's user avatar
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 \...
Noel Arteche's user avatar
1 vote
0 answers
74 views

One way analogues of Logspace

When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$. Likewise we say a function is logspace one-way if the function is ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
114 views

Problems in $P^{PP}$

I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
AITOR GODOY's user avatar
0 votes
0 answers
77 views

On the Reductions of Functional complexity Classes

In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows: Function problem A reduces to ...
Krish Singal's user avatar
2 votes
1 answer
80 views

Complexity of reachability in fractal mazes with traps

Is reachability in fractal mazes with traps EXPTIME complete? A fractal maze includes one or more copies of itself. For example, see the question Decidability of Fractal Maze or Puzzling ...
Dmytro Taranovsky's user avatar
4 votes
1 answer
174 views

Computation with cellular automata in practice

It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate ...
Andi Bauer's user avatar
2 votes
0 answers
77 views

Parallel complexity of fixed dimension fixed constraints integer programming

Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
Turbo's user avatar
  • 12.9k

1
2 3 4 5
14