Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
935
questions with no upvoted or accepted answers
37
votes
1
answer
2k
views
Is it NP-hard to fill up bins with minimum moves?
There are $n$ bins and $m$ type of balls.
The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.
You start with $b_j$ balls of type $j$. Each ball of ...
- 3,023
20
votes
0
answers
661
views
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
- 2,269
19
votes
0
answers
462
views
Is finding a weight-balanced tree NP-hard?
In the following, we consider binary trees where only the leaves have weights.
Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves.
Let $T.l$ and $T.r$ be the left child and ...
- 316
19
votes
1
answer
2k
views
Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.♦
- 152k
15
votes
0
answers
335
views
Is the two-color leapfrog problem in P?
My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem.
I can already show ...
- 738
14
votes
0
answers
203
views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
- 241
13
votes
0
answers
425
views
Choosing a subset of binary variables to maximize the sum of the highest $K$
Consider the following problem:
Input:
integers $n > m > k$;
$n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
$n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).
Let $X_1,\dots,X_n$ be $n$ ...
- 231
11
votes
0
answers
221
views
Covering a complete graph with n copies of an arbitrary graph: NP-complete?
Given a complete graph $G$, an arbitrary graph $H$, and a positive
integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that
their union is $G$, and each of them ...
11
votes
0
answers
396
views
Proof of PCP theorem
I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem".
...
- 3,627
10
votes
0
answers
234
views
Minimum edge deletion partitioning of a planar graph
I'm interested in the time complexity of the following problem:
Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
- 153
10
votes
0
answers
156
views
Complexity class for probabilistic approximation algorithms with bounded error
What's the name of a complexity class of
optimization problems that have
"bounded error probabilistic approximation algorithms"?
Bounded error probabilistic version of APX
(as BPP is bounded error ...
- 560
10
votes
0
answers
1k
views
Universal Turing Machine simulation with bounded time overhead
Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original running-...
- 367
10
votes
0
answers
226
views
"Essential" problem for MA
I am trying to understand different interactive proof systems, in particular AM and MA.
Is there a typical problem for the complexity class MA
as Graph-NonIsomorphism problem is for AM?
Is there ...
- 676
9
votes
0
answers
190
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 105
9
votes
0
answers
324
views
Are there consequences for P ≠ NP that are unintuitive?
It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
- 515
9
votes
0
answers
752
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,048
9
votes
1
answer
426
views
is $P_{CTC} = BPP_{path}$?
I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic.
This is my reasoning, and I would like to know if (1) this is ...
- 191
9
votes
0
answers
336
views
P vs NP and the Time Hierarchy
Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$?
There reason I ask this is that I assume the following:
$$P=NP \implies \forall k\ \exists j.\ \...
- 1,601
9
votes
0
answers
98
views
Interval density of time bounded Kolmogorov complexity
The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
- 12.4k
8
votes
2
answers
444
views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
- 61
8
votes
0
answers
269
views
Complexity of removing edges to eliminate a perfect matching
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
- 81
8
votes
0
answers
89
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
- 287
8
votes
0
answers
352
views
Can any PEG grammar be parsed in linear time?
On the Wikipedia for PEG it is claimed:
Any PEG can be parsed in linear time by using a packrat parser, as described above.
However, packrat parsers can't handle left recursion.
You can eliminate ...
- 12.5k
7
votes
0
answers
302
views
What's the complexity of solving a packing LP?
Linear Programming is in polynomial time weakly
(when numbers are encoded in unary).
AFAIK it remains open if it is possible to solve LP
in polynomial time strongly (when numbers are encoded in ...
- 622
7
votes
0
answers
221
views
complexity of a Constraint Satisfaction Promise Problem
Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem,
I wound up considering the "promise constraint" with 3 boolean inputs that's given by
$C(x,y,z) = \hspace{.1 in}\...
user12859
7
votes
0
answers
150
views
Any Natural Problems shown Easy by Reduction to Horn SAT?
To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing ...
- 363
6
votes
0
answers
164
views
Impossibility of certain type of tree traversal algorithm
I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right ...
- 61
6
votes
0
answers
540
views
What could we say about that conjecture that yields P != NP?
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
- 151
6
votes
0
answers
52
views
Level sums, displacements: how to determine their effect efficiently?
Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.
Define $$S(\delta,m) = ...
- 241
6
votes
0
answers
283
views
Testing algorithm for a modified sieve of Eratosthenes
Context:
I am looking at a modified version of the sieve of Eratosthenes. I started by generalising Eratosthenes' sieve, like so:
Choose some starting "root", $n_0\in\mathbb{N}$, a sieve limit (the ...
- 201
6
votes
0
answers
76
views
Can all computational complexity results be expressed in terms of programming languages?
Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems.
However, on a more formal ...
- 216
6
votes
0
answers
567
views
Can all types of problems be converted to decision problems?
We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well?
Description of the types of problems is ...
- 213
6
votes
0
answers
645
views
Minimum weighted vertex cover on grid graph
Let $G'_{m,n}=(V,E)$ be the grid graph $G_{m,n}$, to which we add "diagonal" edges. For example, here is $G'_{6,3}$:
And for each vertex $v_i \in V$, we have a associated positive value $c_i$
...
- 211
6
votes
0
answers
64
views
Is it possible to reduce functional equations to SAT?
The problem of finding a solution for functional equations can be defined as:
Let A0, A1, A2... An, B0, B1, B2... Bn, X be terms of the lambda calculus, all terms known, except for X, unknown. ...
- 4,047
6
votes
0
answers
142
views
NP-hardness of a special traveling salesman problem
Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$.
Is it NP-hard to solve the traveling ...
- 3,023
6
votes
0
answers
125
views
Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments
One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine.
Is there a ...
- 12.4k
6
votes
0
answers
215
views
On the Turing Completeness of First Order Logic
It is well known that in Descriptive Complexity Theory FO is equivalent to AC0.
However, this accepts a couple of a theory and a string <T,s> iff the ...
- 161
6
votes
0
answers
90
views
Complexity of Set Optimization with Sum of Rational Functions Objective
I encountered the following optimization problem. Let $ S = \lbrace 1, 2, \ldots, n \rbrace $ be a set of items. Each item $ i \in S $ has a non-negative benefit $ b_i \in \mathbb R^+ $, non-negative ...
- 61
6
votes
0
answers
93
views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
- 2,269
5
votes
1
answer
89
views
If P != NP, can every NP-complete language be partitioned into two NP-complete subsets?
Assuming $\mathsf{P} \neq \mathsf{NP}$, then all NP-complete languages are countably infinite. I know not all subsets are NP-complete, but I am wondering if there's a simple proof that every NP-...
- 61
5
votes
0
answers
73
views
Complexity of still life extentions in Game of Life
The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
- 51
5
votes
0
answers
151
views
Is Geometric Disjoint Set Cover in P?
I have come across the following optimisation subproblem:
Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{...
- 193
5
votes
1
answer
297
views
Why the Cook-Levin reduction is not a parsimonious reduction?
In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
- 109
5
votes
0
answers
118
views
The relationship between matrix inversion, the HHL algorithm, and the unlikely scenario that $BQP = PSPACE$
I am studying the quantum computing algorithm presented in the paper Quantum algorithm for linear systems of equations}.
Without going through all the details, the HHL algorithm is able to apply an ...
- 219
5
votes
0
answers
319
views
Reduce factoring to solving quadratic equations
The problem of solving quadratic equations is as follows:
Suppose you are given a set of quadratic equations and are asked to
find $0$-$1$ values for the variables such that all equations are
...
- 51
5
votes
0
answers
408
views
Time complexity of languages recognized by linear bounded automata with restricted number of writes
Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
- 63
5
votes
2
answers
359
views
propositional Modal logic filtration definition
Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition:
$ \mathcal{M} = (W, R, L) $, W is a set of worlds,
...
- 51
5
votes
0
answers
2k
views
Time Complexity of a Knapsack-derived problem
Consider the following problem:
Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
- 141
5
votes
0
answers
315
views
Sokoban with only $k$ boxes
Note: I have posted a hugely expanded version of this question on cstheory.
Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{...
user12859
5
votes
1
answer
221
views
Weakest reduction for P-completeness
It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
- 4,377