Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

15
votes
0answers
264 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
634 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 ...
11
votes
0answers
161 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
231 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 ...
10
votes
0answers
244 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
77 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
115 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
108 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". ...
7
votes
0answers
129 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
232 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
80 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
87 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
52 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
36 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is ...
5
votes
0answers
105 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 ...
5
votes
0answers
84 views

research on OR and AND compression in SAT formulas

this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far. A simple proof that AND-compression of NP-complete ...
5
votes
0answers
55 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
72 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
65 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
61 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
118 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
34 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
63 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 ...
3
votes
0answers
51 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
66 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 ...
3
votes
0answers
71 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
50 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
60 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
37 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 ...
3
votes
0answers
79 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
76 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
36 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
114 views

Proof of SAT is randomly reducible to UNIQUE-SAT

I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani. The proof can be found ...
3
votes
0answers
100 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
149 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
153 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 ...
3
votes
0answers
149 views

For the time hierarchy theorem, how is the input translated efficiently?

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
2
votes
0answers
52 views

Are there online available solved homeworks on complexity theory?

I have never seen this subject before but certain things I read got me curious. I found various online lecture notes on complexity theory and theoretical CS but almost no where do I see solved ...
2
votes
0answers
28 views

AC0 and first order logic equivalence

The page on descriptive complexity theory in Wikipedia states the following: "First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of ...
2
votes
0answers
38 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
2
votes
0answers
292 views

Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a ...
2
votes
0answers
101 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
2
votes
0answers
45 views

EXPTIME and parallel computing

Can we solve an EXPTIME-complete problem in polynomial time given 2^N processors?(N is the size of input).
2
votes
0answers
32 views

Bounded occurrence 3D matching problem

It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching. Informally, Given a set ...
2
votes
0answers
52 views

Notions of computational hardness in terms of information flow?

If we consider polynomial-time (or log-space) computable reductions $<_p^m$ as transformations between computational problems, then the following definitions of known complexity classes suggest ...
2
votes
0answers
83 views

Time Complexity of Simulating CA with TM

This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines. To simulate a CA with a TM, I used a construction which placed a marker on ...
2
votes
0answers
52 views

Complexity of a particular integer knapsack version

I need to know if the following problem is $NP$-complete. The data are as follows : $n$, number of items $\{s_{i}\}_{i \in \{1, \dots n\}}$, item sizes, sorted by ascending values. $S$ knapsack ...
2
votes
0answers
57 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing ...
2
votes
0answers
54 views

End-Of-The-Line Augmented Problem of PPAD

Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line: End-Of-The-Line Problem: $G$ is a (possibly exponentially large) directed ...
2
votes
0answers
58 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ ...