Questions tagged [complexity-classes]
Computational complexity classes and their relations
670
questions
-1
votes
1
answer
72
views
Proof that DFS order is P-complete
Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
1
vote
0
answers
27
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 ...
- 255
-4
votes
0
answers
41
views
would statistical randomness disprove P=NP
I saw a proof that claimed if the 3sat problem was statistically random which by definition means there are no patterns, then a deterministic turing machine could not possibly solve it more ...
8
votes
1
answer
392
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 ...
- 16.9k
1
vote
0
answers
63
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 ...
- 11
0
votes
0
answers
97
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 ...
- 212
2
votes
1
answer
277
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 ...
- 1,330
5
votes
1
answer
387
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 $...
- 27.3k
0
votes
0
answers
166
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 ...
- 101
3
votes
0
answers
111
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,...
- 205
1
vote
1
answer
108
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, ...
- 16.9k
5
votes
0
answers
125
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 ...
- 3,416
12
votes
2
answers
426
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 ...
- 1,761
10
votes
1
answer
805
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 ...
- 113
1
vote
0
answers
77
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.
...
- 900
7
votes
1
answer
293
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 ...
- 16.9k
6
votes
3
answers
332
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 ...
- 11.3k
1
vote
0
answers
132
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. ...
- 19
7
votes
0
answers
188
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. ...
- 1,181
3
votes
1
answer
173
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 ...
- 5,840
2
votes
0
answers
42
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 ...
- 255
3
votes
1
answer
248
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 ...
- 16.9k
0
votes
0
answers
67
views
Are there any examples of problems in ZPP not yet in P?
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?
- 11.7k
9
votes
1
answer
289
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 ...
- 27.3k
10
votes
3
answers
488
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 ...
- 16.9k
0
votes
0
answers
41
views
What the relation between the classes SC and NC?
What the relation between the classes SC (Scott's class) and NC? (Nick's class).
Is SC contained in NC?
Is NC contained in SC?
- 177
3
votes
0
answers
101
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 ...
- 139
1
vote
1
answer
101
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:...
- 1,934
1
vote
0
answers
85
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 ...
- 12.8k
7
votes
0
answers
171
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 ...
- 273
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 ...
- 2,078
3
votes
1
answer
224
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 ...
- 11.3k
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 ...
- 271
2
votes
1
answer
99
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 ...
- 16.9k
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 ...
- 191
6
votes
0
answers
152
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 ...
- 61
2
votes
0
answers
36
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(...
- 21
3
votes
0
answers
99
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 ...
- 131
0
votes
0
answers
139
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
69
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 ...
- 111
3
votes
1
answer
247
views
Relativized world in which P ≠ NP = coNP
Do we know of an oracle relative to which P ≠ NP but NP = coNP?
- 16.9k
4
votes
0
answers
106
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 $\...
- 1,973
4
votes
2
answers
422
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 ...
CommunityBot
- 1
5
votes
1
answer
125
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 $...
- 2,164
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
96
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 \...
- 871
1
vote
0
answers
72
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 ...
- 12.8k
2
votes
0
answers
107
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 ...
- 21
20
votes
4
answers
1k
views
Parity and $AC^0$
Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.
Furst Saxe Sipser to Yao ...
CommunityBot
- 1
9
votes
1
answer
464
views
Cobham's Result on Efficient Computations
In the following paper:
Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland.
Cobham defined the class P ...
CommunityBot
- 1