Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

16
votes
0answers
802 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 ...
16
votes
0answers
331 views

Subset sum problem with many divisibility conditions

Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let $\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
13
votes
0answers
250 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
12
votes
0answers
214 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
11
votes
0answers
272 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 ...
8
votes
0answers
189 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Given $N$ probabilities $P_1,\dots,P_N$ and rewards $R_1,\dots,R_N$ and the integers $M,K$ $(N>M>K)$ as input, define the random variables $X_1,\dots,X_N$ as $$X_i=\begin{cases} R_i & ...
8
votes
0answers
113 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
8
votes
0answers
123 views

“Essential” problem for MA

I am trying to understand different interactive proof systems. Is there a typical problem for the complexity class MA (like graph-nonisomorphism is for AM)? Is there a problem in MA but not known to ...
7
votes
0answers
77 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
7
votes
0answers
58 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
7
votes
0answers
339 views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
7
votes
0answers
139 views

$NEXP = \Sigma_2 \implies NEXP = MA$?

Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds? (The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
7
votes
0answers
295 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 ...
6
votes
0answers
181 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 ...
6
votes
0answers
86 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 ...
6
votes
0answers
92 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 ...
6
votes
0answers
61 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 ...
5
votes
0answers
82 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 ...
5
votes
0answers
72 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 ...
5
votes
0answers
66 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 ...
5
votes
0answers
87 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 ...
5
votes
0answers
69 views

'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game: Intance of 'Stones' game is: finite set $X$ relation $R \subseteq X^3$ set $Y \subseteq X$ and ...
5
votes
0answers
65 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 ...
5
votes
0answers
122 views

Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$

Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$. We are interested to find $$ \max_{\pi\in S_n}\left( ...
4
votes
0answers
41 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 ...
4
votes
0answers
107 views

If one shows s that UNIQUE k-SAT is in P, does it imply P=NP?

Valiant & Vazirani proved SAT transforms UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, ...
4
votes
0answers
83 views

What are appropriate isomorphisms between formal languages?

A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are ...
4
votes
0answers
39 views

PTAS vs. exact-time sub-exponential algorithms

I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely ...
4
votes
0answers
43 views

Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph

I know that Hamiltonian cycle problem in 3-regular triangle-free graphs is NP-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C_3$ cycle, What is ...
4
votes
0answers
68 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 ...
4
votes
0answers
162 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land ...
3
votes
0answers
46 views

Adleman's theorem to $\mathsf{P=BPP}$

Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$ Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$? Does it mean Adleman's result could be ...
3
votes
0answers
53 views

Is integer sorting possible in O(n)?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
3
votes
0answers
77 views

Relativization of NP-completeness

This is actually exercise 3.7 from "Computational Complexity: A Modern Approach". I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
3
votes
0answers
85 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
3
votes
0answers
64 views

Graph canonization is not a decision problem. But what type of problem is it?

I noticed that the most convenient way to deal with quotient structures (like the rational numbers or other equivalence classes) within ZFC is to select a unique representant from each equivalence ...
3
votes
0answers
76 views

Is finding all valid nets of a polyhedron NP-hard?

Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard? My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number ...
3
votes
0answers
55 views

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT? We can use the Valiant Vazirani Therom, also found here (in more detail). Essentially, it is a randomized algorithm that ...
3
votes
0answers
67 views

Packing rectangles to generate a sprite sheet

I am writing a sprite sheet generator tool in adobe AIR, and I have to force with the question: How to pack a collection of 2D rectangles to smallest possible 2D rectangle with power of two. (like ...
3
votes
0answers
82 views

How to eliminate for/if/while from algorithms when it's possible

Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive ...
3
votes
0answers
94 views

PARITY using depth one TC0 circuit

I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
3
votes
0answers
39 views

Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems

We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to ...
3
votes
0answers
148 views

Not self-reducible NP problem

I am interesting in proving that there is no search problem that is polynomial bounded and self-reducible, as long as ${\sf P} \neq {\sf NP} \cap {\sf coNP}$. The problem is I don't know how to ...
3
votes
0answers
162 views

Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
2
votes
0answers
27 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP" The main result is that if there is a sparse set $S \in NP$ such that $coNP ...
2
votes
0answers
37 views

Disco Zoo Complexity

A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 ...
2
votes
0answers
125 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction. This class is known as PSPACE-complete. ...
2
votes
0answers
48 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
2
votes
0answers
28 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
2
votes
0answers
81 views

Is this modification of the subset-sum problem NP-complete?

Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, ...