# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,904 questions
Filter by
Sorted by
Tagged with
46 views

### Boolean vs algebraic circuits difference

Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized. What is the central reason such a ...
• 12.5k
134 views
+50

### Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene  (https://dl.acm.org/doi/10.1145/62212.62255). Specifically, I was trying to look at the $1.82$...
• 101
83 views

• 12.5k
26 views

### NCness of unique solution fixed dimension integer programming

Consider the promise problem of fixed dimension integer programming with promise being that there is exactly one witness. The problem is in $TFNP$. If the promise problem is in $FNC$ then integer $GCD$...
• 12.5k
67 views

### Interactive proofs with computation bounded Merlin

Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits) where computation power of Merlin is bounded by polynomial-size circuits. For example, every unary NP-...
• 1,695
1 vote
67 views

### Examples of promise search problems that are easier than their non-promise variants?

By promise search problem, I mean a search problem for which the solution is guaranteed to exist (e.g. find a solution to a linear system of equations, knowing that a solution does exist). Are there ...
• 209
222 views

### Classes between PH and PSPACE

I am interesting in languages of the following form: $x \in L \Leftrightarrow Q y_1 Q y_2 \ldots Q y_n P(x, y_1, \ldots y_n, x).$ Here every Q is $\forall$ or $\exists$; $n$ is the length of $x$, the ...
• 1,695
51 views

### Running time of SAT and other EXPTIME algorithms [closed]

I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
1 vote
140 views

### Complexity of "discrete-time" SAT

I'm interested in the complexity of deciding satisfiability of the following family of formulae: $\exists j. I[j(0)] \land \forall t. S[j(t),j(t+1)]$ where: $j:\mathbb{N} \to \{0,1\}^n$ has finite ...
• 767
297 views

### Is any computational complexity question solved by injury priority method except Post problem?

As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree? ...
• 1,059
68 views

### Solving MDPs with polytope action spaces

A (finite) Markov Decision Process (MDP) consists of a finite set of states $S$, a finite set of actions $A_s$ which we will allow to depend on the state $s\in S$, an initial state $s_0\in S$ (the ...
• 2,161
177 views

### What Complexity Class is this? Is this already known?

Let's call this the Path Game. For this example, lets imagine a 16x16 grid: Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
• 39
118 views

### Is orthogonal polygon with crossings count NP-complete?

The are several NP-complete problems related to the construction of orthogonal polygons. Rapport showed that it is NP-complete to to decide the existence of orthogonal simple polygon that passes ...
119 views

### why is relativization of computational complexity so versatile？

Computational complexity has natural absolute measurement, such as linear, polynomial, exponential, etc. But observations or results are almost relativized, or relational. And even relational ...
• 1,059
127 views

### Cook's theorem and universal machine

From Papadimitriou and Yannakakis, "A Note on Succinct Representations of Graphs" second parragraph of the proof of the main result. Cook (1971) presented in his classical paper a ...
• 767
120 views

### (PCP theorem) Any natural decision problem defined in the format of PCP-verifiers?

Is there any natural decision problem that "trivially fits" the definition of a PCP-verifier? I mean, a problem precisely defined as follows: given a set of constraints (each one depending ...
82 views

### Is logic in computation of computation constructivist?

Is logic in computation of computation constructivist? I think so, because dynamic languages ​​are comparable to constructivist set theory (try a demonstration of the axiom of choice in computing: it ...
107 views

### What is the intuition behind P/qpoly=P/poly?

I very much struggle to understand the qualitative differences between anything/qpoly. For exampe we read at Watrus that BQP/qpoly essentially are the decision problems that are solved by polynomial ...
• 141
143 views

### Information theoretic arguments for complexity

This Wikipedia article,Decision tree model, states that decision tree complexity lower bound $O(n \log_2 n)$ for sorting problem is information theoretic since any algorithm ( modeled as decision ...
51 views

### Polytime reduction to factoring variant of subset sum

I'm interested in simple step explanation of reduction from CNF SAT(preferably) / subset sum to decision problem mentioned in this answer and this topic. E.g. given either CNF formula or set of ...
1 vote
78 views

### Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
• 429
1 vote
133 views

### Looking for an implementation of any PCP-verifier for any NP problem

Is there any implementation of any PCP-verifier (for any NP problem) researchers can download and test? No matter if it is a github entry with actual downloadable code or just a (reasonably detailed) ...
74 views

### Finding Hamilton cycles in random graphs

For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)? If this is an open problem, I will also accept an empirically ...
• 2,362
1 vote
78 views

### Decision vs search problem specification

Let us suppose we have a sort function. One way of specifying it is to say that a sort function is any function where if the input/output are vectors $I, O$, then $O_i \leq O_j \forall i < j$ and ...
• 1,301
327 views

### Is the Church-Turing thesis a theorem? Conjecture? Axiom?

One thing I was never clear on when taking Computational Complexity in college is whether the Church-Turing "thesis" is (or can be) proven. Is it.. A theorem? If so, where's the proof? A ...
1 vote
199 views

### What if NP = coNP?

Are there any major implications of NP = coNP (if true) the way there would be if P=NP? I'm thinking of real-world implications analogous to the encryption-pocalypse (excuse the drama) that would ...
• 33
103 views

### Are there well-accepted attempts of people to create complexity classes in continuous time?

I'm not in CS theory, but I've talked to a complexity theorist recently who, in passing, suggested that my research (not really analog computing, but hypercomputation using physical systems in ...
1 vote
106 views

### How to measure the weirdness of algorithms?

Let $M$ is a polynomial $k$-tape Turing machine and $C^t(x)$ is a time-bounded Kolmogorov complexity. Let $str_M(x)$ be a string of the following form: str_M(x)=w_1^1\# w_2^1 \# ... \# w_{m}^1 ■ w_1^...
• 49
153 views

### Containment: deterministic versus with probability one

As I was browsing the Complexity Zoo, I came across this statement: Relative to a random oracle, PH is strictly contained in PSPACE with probability 1 [Cai86]. What confused me was the addition of &...
• 123
181 views

### Consequences of efficient algorithm for search problem unique 3SAT

The decision problem Unique SAT ={$\phi$  has unique satisfying assignment } represents a class of computational problems. P=NP iff Unique SAT is in P. Notice that Unique SAT is CoNP-hard and Unique ...
82 views

### Sparsity Bounds for Probabilistic Polynomials

Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority? A probabilistic polynomial is a distribution of polynomials $D$ such that ...
• 71
71 views

### What's the difference between 'theoretical' and 'applied' runtime complexity?

I recently followed a course on complexity theory and according to the professor I got one particular question wrong. The question involved the runtime complexity of checking the correctness of a ...
• 1
311 views

### How many multiplications are needed to compute the determinant of a 3×3 matrix?

In a comment on this question in 2016, Jeffrey Shallit remarked: I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute ...
1 vote
90 views

### Efficient enumeration of connected functional digraphs (up to isomorphism)

Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
1 vote
84 views

### Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets

In the Exact Cover by 3-Sets problem, we are given a set $X = \{x_1, x_2,\ldots, x_{3n}\}$ and a family of subsets $F = \{\{x_{i_1}, x_{i_2}, x_{i_3}\}\}$ of 3-element subsets of $X$. The question is ...
• 11
301 views

### Lower-bounds under SETH

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are ...
• 161
119 views

### Does NP Completeness always fall on one side or the other of an intermediate computation?

Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete ...
• 2,313
91 views

### Showing that a modification of an NP-Complete problem is also NP-Complete

In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I ...
545 views

### Best known algorithm for NEXP-complete problem

What is the best (in time) algorithm for NEXP-complete problems? Is there an algorithm that solve a NEXP-complete problem in time $2^{o(2^n)}$?
• 1,695
131 views

• 99
125 views

### Computing permanents when we are promised that the value of the permanent is large

Suppose you are given an $n$ by $m$ real matrix (or even complex matrix) with orthonormal rows. ($m=poly(n)$, say $m=n^2$.) For an $n$-tuples of columns (with repetitions) from M we consider the ...
• 6,083
59 views

### Pebble games and conversions to bounded width circuits

Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits? Here, "conversions to bounded width circuits" means that circuits ...
181 views

### Complexity of the Complete (3,2) SAT problem?

A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies. Deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem ...
• 1,069
76 views

### Nondeterministic polynomial time languages with linearly bounded certificates

Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
• 91
Let $f$ be a boolean function on $n$ variables - say we want to find the smallest circuit $C$ where $C(x)=f(x)$ for all but an $\epsilon$ fraction of inputs $x \in \{0,1\}^n$. What is known about the ...
The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W-hard. Is it also W-hard when parameterized by $k$ plus the number of subsets in the instance? I explain in a ...