Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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
5 votes
0 answers
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 [1988] (https://dl.acm.org/doi/10.1145/62212.62255). Specifically, I was trying to look at the $1.82$...
0 votes
1 answer
83 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} = \...
  • 173
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,...
  • 12.5k
-1 votes
0 answers
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
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
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
3 votes
2 answers
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 ...
0 votes
1 answer
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
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
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? ...
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 ...
  • 2,161
0 votes
1 answer
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
0 votes
0 answers
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 ...
-1 votes
0 answers
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 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 ...
4 votes
0 answers
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 ...
-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 ...
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 ...
  • 141
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 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 ...
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 ...
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 ...
  • 1,301
0 votes
4 answers
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
1 answer
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
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
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
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 &...
  • 123
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 ...
3 votes
0 answers
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
0 votes
0 answers
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
26 votes
1 answer
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
0 answers
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
1 answer
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
6 votes
1 answer
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
8 votes
0 answers
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
-1 votes
1 answer
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 ...
0 votes
2 answers
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)}$?
0 votes
1 answer
131 views

The Complexity of Multi-Objective Optimization

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
  • 57
0 votes
0 answers
64 views

Short UNSAT Certificates for X3SAT

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
4 votes
0 answers
75 views

Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al. Are there similar results for ($k$-uniform)...
  • 41
0 votes
0 answers
68 views

Simplify or bound using Big-O notation

I was following a research paper which have the following equation: $\left(1-\frac{1}{K}\right)^{K-i}\left[1-\left(1-\frac{1-p}{K}\right)^{i}\right]=\frac{i(1-p)}{K}+O\left(\left(\frac{i}{K}\right)^{2}...
7 votes
0 answers
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
2 votes
0 answers
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 ...
2 votes
1 answer
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 ...
2 votes
0 answers
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
5 votes
0 answers
82 views

Complexity of approximating boolean functions with circuits

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 ...
0 votes
1 answer
70 views

Parameterized complexity of Hitting Set with slightly bigger parameter

The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W[2]-hard. Is it also W[2]-hard when parameterized by $k$ plus the number of subsets in the instance? I explain in a ...

1
2 3 4 5
59