Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
1 vote
0 answers
57 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....
15 votes
1 answer
937 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
34 votes
2 answers
3k views

NTIME(n^k) ≠ DTIME(n^k) ?

In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that $\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$. ...
0 votes
0 answers
71 views

3SAT instances where no assignment fails to satisfy more than one clause: do they eixst, and what complexity class do they belong in?

Title says it all. I am curious of the 3SAT problem but limited to instances where only one clause is left unsatisfied by any literal assignment. Do such problems exist, and if they do, what is it ...
16 votes
3 answers
356 views

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

Apologies in advance if this question is too simple. Basically, what I want to know is if there are any functions $f(x)$ with the following properties: Take $f_n(x)$ to be $f(x)$ when the domain and ...
4 votes
0 answers
216 views

Complexity of Computing Shannon Entropy

It is my understanding that the necessity of numerical precision can be an obstacle when trying to show a decision problem's membership in a particular complexity class. For example, I believe it is ...
16 votes
4 answers
3k views

What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing ...
-1 votes
1 answer
85 views

Does the set $P$ contain only decision problems or also optimization problems? [closed]

Looking at many posts on Stack Overflow, it seems the set $P$ has only decision problems. See for instance the accepted answer here. But, this seems to be in contradiction to the book Introduction to ...
5 votes
0 answers
176 views

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 [1988] (https://dl.acm.org/doi/10.1145/62212.62255). Specifically, I was trying to look at the $1.82$...
0 votes
0 answers
62 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 ...
0 votes
1 answer
86 views

On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

Introduction I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \...
28 votes
6 answers
3k views

Are there NP-complete problems with polynomial expected time solutions?

Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)? If not, are there problems for ...
0 votes
0 answers
46 views

Polynomial GCD exact complexity in terms of degree and number of variables

https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
-1 votes
0 answers
27 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$...
4 votes
0 answers
119 views

Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
0 votes
0 answers
121 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 ...
3 votes
2 answers
228 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 ...
16 votes
0 answers
410 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

I am interested in the following problem. Node Multiway Cut on Planar Graphs with terminals on the outer face Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which ...
0 votes
0 answers
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 vote
2 answers
69 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 ...
0 votes
1 answer
53 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
1 answer
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 ...
2 votes
1 answer
301 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? ...
3 votes
0 answers
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 ...
0 votes
1 answer
181 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 ...
-1 votes
1 answer
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 ...
19 votes
1 answer
902 views

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear equations ...
4 votes
0 answers
122 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 ...
39 votes
4 answers
3k views

Techniques for showing that problem is in hardness "limbo"

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
-1 votes
1 answer
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 ...
-1 votes
1 answer
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 ...
3 votes
1 answer
906 views

Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

i have some question concerning the class PP and PPT machines. PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability < ...
4 votes
0 answers
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 ...
0 votes
1 answer
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 ...
1 vote
0 answers
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 ...
1 vote
0 answers
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) ...
2 votes
0 answers
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 ...
42 votes
23 answers
5k views

What hierarchies and/or hierarchy theorems do you know?

I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, ...
1 vote
0 answers
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 ...
17 votes
1 answer
1k views

Ranking the Difficulty of NP Hard Problems in Practice

This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard ...
0 votes
4 answers
329 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 ...
6 votes
1 answer
455 views

How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of ...
39 votes
9 answers
4k views

Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
1 vote
1 answer
200 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 ...
5 votes
0 answers
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
0 answers
107 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^...
4 votes
4 answers
490 views

Are there alternatives to using polynomials in defining the different notions of efficient computation?

Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an ...
16 votes
1 answer
502 views

How expensive may it be to destroy all long s-t paths in a DAG?

We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
2 votes
1 answer
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 &...
4 votes
0 answers
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 ...

1
2 3 4 5
59