Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

898 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
644 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
19 votes
1 answer
1k 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 ...
  • 147k
18 votes
0 answers
451 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 ...
  • 306
15 votes
0 answers
329 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 ...
14 votes
0 answers
180 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
420 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
214 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
384 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". ...
10 votes
0 answers
230 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
988 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
220 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 ...
9 votes
0 answers
188 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
317 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 ...
  • 505
9 votes
0 answers
741 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 ...
9 votes
1 answer
409 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 ...
9 votes
0 answers
328 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
94 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.3k
8 votes
2 answers
387 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 ...
8 votes
0 answers
257 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
88 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
334 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.4k
7 votes
0 answers
297 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 ...
7 votes
0 answers
219 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}\...
user avatar
7 votes
0 answers
148 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 ...
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 ...
6 votes
0 answers
538 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) = ...
6 votes
0 answers
280 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 ...
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
475 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 ...
6 votes
0 answers
604 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
63 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,017
6 votes
0 answers
141 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
124 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.3k
6 votes
0 answers
212 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 ...
6 votes
0 answers
92 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
70 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,...
5 votes
0 answers
149 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
265 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
117 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 ...
5 votes
0 answers
314 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 ...
5 votes
0 answers
390 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
328 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
309 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{...
user avatar
5 votes
1 answer
209 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-...
5 votes
0 answers
127 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,...

1
2 3 4 5
18