Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

15
votes
0answers
245 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
620 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 ...
13
votes
0answers
361 views

Proving the (in)tractability of this Nth prime recurrence

As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
11
votes
0answers
149 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
227 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
240 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
72 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
364 views

Google Code Jam Great Wall Problem

So, Google Code Jam round 1C has just wrapped up, and one of its problems seems rather elusive to me: https://code.google.com/codejam/contest/2437488/dashboard#s=p2 A quick summary of the problem is ...
8
votes
0answers
114 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
100 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
219 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
42 views

What do complexity classes look like, if we use Turing reductions?

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this: (under standard conjectures). I'm sure we're all ...
6
votes
0answers
71 views

Almost always almost right

What's the name of a complexity class of optimization problems that have BPP approximations? That is, I'm looking for a class of problems that relates to APX as BPP relates to P.
6
votes
0answers
51 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
96 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
79 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
69 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
27 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 ...
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 ...
4
votes
0answers
97 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
50 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
58 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
48 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
57 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
31 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 ...
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
78 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
75 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
113 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
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
152 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
145 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
48 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
22 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
35 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
269 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
98 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
44 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
31 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
51 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 ...