The 2024 Developer Survey results are live! See the results

# Questions tagged [complexity]

The tag has no usage guidance.

93 questions
Filter by
Sorted by
Tagged with
103 views

### Collapse of query and oracle hierarchies

Let ${\tt QH}$ stand for the Query Hierarchy, defined as the union of all classes ${\tt P}^{{\tt NP}[k]}$, of problems solvable by polynomial time machines making at most $k$ queries to ${\tt NP}$ and ...
• 120
1 vote
79 views

### Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard: ...
• 171
87 views

### Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
91 views

### The role of Turing machines in computational complexity [closed]

In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
• 99
98 views

### Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances

I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances. input and output: input: A satisfiable cnf ...
• 316
201 views

### What’s the complexity of this decision problem with bit shifting?

I’ve been wondering about the computational complexity of a problem that involves bit shifting. Let me define some notation before I present the problem. If $\langle{b}\rangle$ is a bitstring ...
• 196
412 views

### What are some examples of decidable Natural Problems outside of EEXP?

I haven't really seen any examples of problems in complexity classes higher then EEXP. What are some examples of some primitive recursive problems outside of EEXP? Ideally with a large number of Es, ...
• 353
301 views

### is SUBEXP contained within PSPACE?, NP?

Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...
• 353
36 views

### Hardness of finding minimal subsets that will change the maximum of a univariate polynomial

Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
101 views

### Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover

This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
82 views

### How is FNP defined? Or, is FNP closed under relaxation?

I hope this isn't a dumb question, but I've been driving myself nuts regarding the following. The definition of $\mathsf{FNP}$ that I've found in many places is the following: A relation $R(x,y)$ is ...
82 views

### What's the exact complexity of a DFS if we revisit nodes?

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
130 views

### Complexity of "opposite" version of a variant of #Positive-2-SAT

In this post ,I introduced a new variant of #Positive-2-SAT . This version of problem puts restrictions on the inputs of the #Positive-2-SAT such that we can only choose at max only 2 clauses from ...
• 13
### Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?
Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ? I have found a proof for this ...