Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,953
questions
4
votes
0
answers
72
views
MIP with bounded communication between provers
Are there any known results on the complexity class that is MIP except with independence of provers loosened to allow "limited classical communication" between provers: where total message ...
- 141
2
votes
0
answers
108
views
Question about #P-completeness and NP-completeness
In the book Nature of Computation by Moore & Mertens there is an exercise saying "show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every ...
- 21
1
vote
0
answers
18
views
Coloring the $k$-deletion graph “constructively”
For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$.
My question is: fixing $k>1$, does there exist some $C=C_k$ ...
- 518
0
votes
0
answers
94
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 ...
- 101
4
votes
0
answers
302
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 ...
2
votes
0
answers
68
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....
- 12.6k
-1
votes
1
answer
92
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 ...
- 109
0
votes
0
answers
76
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.6k
6
votes
1
answer
296
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$...
- 13
0
votes
1
answer
100
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
54
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.6k
0
votes
0
answers
70
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,859
1
vote
2
answers
71
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
267
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,859
1
vote
1
answer
63
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 ...
- 11
1
vote
1
answer
167
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 ...
- 889
2
votes
1
answer
309
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,050
3
votes
0
answers
73
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,151
0
votes
1
answer
199
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 ...
- 21
0
votes
0
answers
141
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 ...
- 20.7k
-1
votes
1
answer
140
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 ...
- 889
4
votes
0
answers
131
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 ...
- 373
-1
votes
1
answer
85
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
120
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
149
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 ...
- 20.7k
1
vote
0
answers
84
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 ...
- 557
1
vote
0
answers
139
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) ...
- 373
2
votes
0
answers
80
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,402
1
vote
0
answers
79
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
381
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
214
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
114
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
114
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
156
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
185
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 ...
- 20.7k
3
votes
0
answers
87
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
75
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
27
votes
1
answer
374
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 ...
- 761
1
vote
0
answers
97
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
103
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
312
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
120
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,333
-1
votes
1
answer
126
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 ...
- 99
0
votes
2
answers
607
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,859
0
votes
1
answer
167
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
1
answer
104
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 ...
- 519
4
votes
0
answers
76
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}...
- 99
8
votes
0
answers
194
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 ...
- 5,973
2
votes
0
answers
61
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 ...
- 689