Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
994
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
21
votes
0
answers
695
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,279
20
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.♦
- 156k
19
votes
0
answers
484
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
17
votes
0
answers
357
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 ...
- 758
14
votes
0
answers
224
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
432
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
243
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
401
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,657
10
votes
0
answers
236
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
158
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 ...
- 570
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
234
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 ...
- 686
9
votes
0
answers
201
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
331
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
765
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
445
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
376
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.7k
9
votes
0
answers
346
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,611
9
votes
0
answers
99
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
514
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
1
answer
303
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
91
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
7
votes
0
answers
306
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
222
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
152
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
172
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\...
- 161
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
284
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
79
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 ...
- 286
6
votes
0
answers
640
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
664
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
70
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,117
6
votes
0
answers
143
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
127
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
219
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,279
5
votes
0
answers
77
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
153
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
336
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
120
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
324
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
425
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
0
answers
155
views
Interactive proofs for coNP languages proof clarification
I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the ...
- 61
5
votes
2
answers
378
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
316
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
0
answers
128
views
Reduction from clique to bag automata
I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem:
Bag Automaton:
A non deterministic finite state automaton $M=(Q,I,s,...
