Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

7
votes
1answer
271 views

DNF to CNF conversion: Easy or Hard

In relation to the thread CNF to DNF — conversion is NP Hard (and a related Math thread): How about the other direction, from DNF to CNF? Is it easy or hard? On Page 2 of this paper, they seem to ...
0
votes
1answer
17 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
6
votes
0answers
174 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 ...
-3
votes
0answers
27 views

EQ NFA p-space complete

Who originally proved that eq nfa is p-space complete. Could someone provide me with a reference to the paper where it was originally proved.
1
vote
0answers
29 views

Open problems in complexity theory [closed]

I am looking for open problems in complexity theory that an undergrad might have any possibility of tackling.
3
votes
1answer
59 views

About codes over $\mathbb{F}_2$

I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for! So any set of binary ...
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 ...
0
votes
0answers
22 views

How many processors does STCON need on a PRAM?

I'm trying to understand why the s-t connectivity (STCON) problem is in NC. In order to be in NC, a problem must have an algorithm that is O((log n)^c) time and O(n^k) processors where c, n are ...
2
votes
2answers
68 views

Consequences of $NP=coNP=BPP=RP$

What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?
2
votes
0answers
124 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. ...
5
votes
1answer
104 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
2
votes
1answer
31 views

Constructing solution to 3SAT formulas using oracle queries [duplicate]

I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula ...
4
votes
1answer
234 views

Does NP-completeness require to find the solution?

In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem: Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$: if ...
2
votes
0answers
26 views

Proof sketch that NP total search problems cannot be NP-complete [duplicate]

From a blog post, about proving that NP total search problems cannot be NP-complete unless NP=co-NP. It's possible to write a convincing proof sketch as follows. Consider what would it would mean ...
0
votes
0answers
15 views

From hypercontractivity norm bounds to small set expansion property

Consider these two theorems on this theme, Lemma 8 on page 10, http://www.boazbarak.org/sos/files/lec2d.pdf Lemma B.1 on page 63 of http://arxiv.org/pdf/1205.4484v3.pdf Aren't these two theorems ...
10
votes
1answer
102 views

Proof of Karp-Lipton theorem

I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009). In particular, this book states the following: ...
-2
votes
0answers
24 views

Polynomial verifier in computation theory (Schedule Problem)

P is an integer and M a matrix such as M ∈ {0,1}^k×m, M(i,j) = 1 signifies that a student i is inscribed in the activity j question: is there a Schedule at most P period that allows us to place ...
-2
votes
1answer
38 views

Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility

Given a gate called Nand with the following truth table: A | B | A Nand B ------------------ 0 | 0 | 1 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 We can ...
1
vote
1answer
68 views

What can I deduce if an NP-complete problem is reducible to its complement?

Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I ...
0
votes
1answer
47 views

Poly-time reduction: D and D Comp [duplicate]

Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function. I will ...
-1
votes
0answers
24 views

How do I prove that 1 function is an upper bound of the other? [duplicate]

If for every $n > 0$ and some $b > 1$, $T(n) \le h(n)$ and $h(n) = O(h(n/b))$ then how can I prove that $T(n) = O(h(n))$, I understand that $T$ is bounded by $h$, so $h$ must be its upper bound, ...
-4
votes
1answer
29 views

Complexity if special case of SAT

I have the following problem: How to show that the special case of SAT, in which each clause has either exactly two literals or at most one negative literal, is NP-complete?
0
votes
1answer
31 views

What is a sufficiently complex system?

I have been reading about the AI approaches, and I came across the AI emergent approach that has the following definition: That is, the appearance of an entity with a sense of its own identity and ...
3
votes
1answer
68 views

Optimization in multivalued logic. Optimal strings with given patterns

This question comes from an application in multivalued logic. Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the ...
2
votes
1answer
64 views

Are there name and literature for this SAT-like problem?

Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$, we define $\textsf{Prob}(f,n)$ as the following problem: Find an $x \in \{0,1\}^n$ such that $f(x) = 1$. A machine solving ...
1
vote
1answer
33 views

Complexity of recognizing whether two $\omega$-regular expressions represent the same language

If the complexity of recognizing whether two regular expressions represent different languages is EXPSPACE-complete, then what can be said for the complexity of recognizing whether two ...
2
votes
1answer
47 views

Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
1
vote
2answers
83 views

Why is Oracle Turing Machine important?

As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design ...
-2
votes
0answers
14 views

A set of languages over {0, 1} which does not belong to Recursively Enumerable set are uncountable [closed]

I have a problem of Theory of Computation i.e. Prove that A set of languages over an alphabet Σ = {0, 1} which does not belong to Recursively Enumerable set, are uncountable. Anyone can ...
7
votes
4answers
198 views

Can finding a witness be NP-hard even if we already know there is one?

The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand. Suppose that we have a problem in which ...
0
votes
0answers
72 views

Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
1
vote
1answer
83 views

P-Completeness and Reducibility

I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance. The problem I'm stuck on is proving that the empty ...
2
votes
3answers
73 views

Could an NP-Hard problem be in P in after a basis transform? [closed]

I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked. So here goes: Take the following problem for example: Let ...
-1
votes
2answers
188 views

Some inference about NP

this is my first question on this site. I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me. I) each NP problem can be ...
1
vote
1answer
41 views

How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

How can TSP be an NP-optimization problem ? The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and ...
20
votes
4answers
2k views

Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
1
vote
0answers
64 views

Totally unimodular <=> polynomial time?

Crossposting due to recommendation. I formulated a MIP problem which I didn't expect to be unimodular. The problem is to find a minimum complete sequence in a strongly connected digraph. That is, ...
0
votes
1answer
58 views

What's the complexity of the Bombe?

Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious. While watching the Imitation Game, ...
0
votes
1answer
62 views

Array search NP completeness

Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time. If we let h = log n then it takes O(2^h) time. Notice that if the array is ...
17
votes
3answers
1k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
1
vote
1answer
26 views

Particular function communication complexity computation

Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then ...
2
votes
1answer
19 views

Complexity of self-reducible set

I am trying to solve the following problem: A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where ...
1
vote
0answers
30 views

Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, ...
0
votes
1answer
24 views

Complexity bound on $RP^{RP}$

This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in ...
0
votes
0answers
37 views

Relationship between functions and formal languages?

PR is defined as "the complexity class of all primitive recursive functions" and also equivalently as "the set of all formal languages that can be decided by such a function". ...
3
votes
2answers
57 views

Restricted Integer Programming

The integer feasibility problem is NP-complete: $Ax=b, x \geq 0, x \mbox{ integer}$ $A$ contains elements in $\mathbb{R}$ If we restrict this: $A$ contains only elements in: $\{1,0\}$ ...
4
votes
1answer
130 views

Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
1
vote
1answer
44 views

FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?
3
votes
1answer
29 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
0
votes
0answers
14 views

Subexponential algorithm for Np-complete problems [duplicate]

http://cstheory.stackexchange.com/a/3627/32204 Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!