Questions about finding mappings between problems that allow solving one problem using a solution of another one.

learn more… | top users | synonyms

0
votes
0answers
6 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 ...
1
vote
1answer
32 views

Half-SAT intractability proof

I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows: Half-SAT is a problem where C is a CNF boolean ...
3
votes
2answers
350 views

Is it allowed to do a binary search with an oracle when proving NP-completeness?

In http://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, ...
4
votes
0answers
89 views

Bin packing with twin items

Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no ...
4
votes
0answers
68 views

Is it possible to boost the error probability of a Consensus protocol over dynamic network?

Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
-1
votes
0answers
45 views

How can I prove that scheduling problem F2//Lmax is NP-Hard?

I'm trying to solve it via reduction to the 2-Partion problem. All online resource are leading to a single solution, which is: http://i.imgur.com/mkPrCzb.png (taken from ...
2
votes
1answer
55 views

I want to figure out whether my problem described below is reducible to the set cover problem

I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$. I need an algorithm that gives me a set $T$ of minimum cardinality ($T ...
2
votes
3answers
62 views

Reduction from $L_{nonuniversal}$ to $L_{finite}$

As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly. Given are two languages $L_{finite}$ and ...
-3
votes
1answer
42 views

Is $H_0$ reducible to $\overline H_0$?

Be $H_0$ the special halting problem with $$H_0 = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace^* | \varepsilon \in L(M)\rbrace$$ and $\overline{H_0}$ being its complement. Is $H_0$ reducible to ...
1
vote
1answer
33 views

How to turing reduce equivalent languages $Q$ to infinite language $I$

Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$ I'm trying to Turing reduce $Q$ to $I$ ...
3
votes
1answer
77 views

Covering a polygon with n circular rings

Question 1: Why we can/can't solve the following problem using a geometric constraint solver? Question 2: Is there any algorithm to solve this problem? Question 3: Can we reduce this problem into some ...
2
votes
1answer
69 views

Proof by Turing Reduction

I need to proof the following by turing reduction. Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = ...
4
votes
1answer
293 views

Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, ...
7
votes
2answers
63 views

Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time. $$LIN \subseteq P$$ Since HORN-SAT is solvable in $O(n)$ (as ...
1
vote
1answer
17 views

How can I convert a list with duplicates into a set for a reduction to the set cover problem?

I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here. Here's a condensed version of the problem: You're given a collection ...
4
votes
0answers
43 views

Proof that P is closed against switching between polynomially related encodings

Lemma 34.1 Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and ...
1
vote
1answer
52 views

NP Complete Subset GCD Proof

$SubsetGCD$ is described by the following: instance: A set of positive integers $S$ and an integer $k$ question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$ ...
1
vote
1answer
30 views

Showing NP-hardness by reducing from a search problem

I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem. ...
0
votes
0answers
42 views

Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
0
votes
1answer
47 views

Reduction of SUBSET-SUM to SET-PARTITION [duplicate]

There is a similar question that has been asked, but my question addresses particular detail of an answer. I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description: ...
3
votes
1answer
53 views

How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia) I know that the problem of counting the ...
4
votes
1answer
42 views

Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
1
vote
1answer
66 views

Checking acceptance of a word vs finding an accepted word

We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM? Are these two problems related in some ...
1
vote
1answer
45 views

Do problems in P only reduce to NP and coNP problems?

Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$. Statement: $B\in P, D\in NP, C\in coNP$. Is the statement true for every $B,C,D$? I know that the answer is no and I have ...
1
vote
2answers
49 views

$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$? Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial ...
0
votes
0answers
29 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
6
votes
1answer
132 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 ...
3
votes
0answers
41 views

Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
7
votes
0answers
39 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
2
votes
1answer
56 views

Relation between the “Point-Cover-Interval” problem and the “Interval Scheduling” problem

Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains ...
2
votes
1answer
67 views

Prove Vertex-Cover of maximum degree 3 is NPC

This is a homework question. I need to prove that the following language is in NP Complete: 3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most ...
-1
votes
1answer
64 views

Determine if the language is $R$

Consider the following language: $$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$ determine whether or not the language is in $R$. Now, from my ...
0
votes
3answers
66 views

Reduction and decidability

Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$ I am trying to understand the following proof that this language $L$ is ...
2
votes
1answer
54 views

Cycles in hardness of ST-CON for the class NL

It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete. I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction ...
3
votes
0answers
52 views

smallest satisfiability-equivalent formulas (generalized Tseitin transform)?

What is known about the following optimization problem for formulas in propositional logic: input: formula $F$ output: formula $G$ in CNF with $\mathrm{Var}(G) \supseteq \mathrm{Var}(F)$ such that ...
-2
votes
1answer
60 views

If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true? If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete. Intuitively I think the answer is No because ...
0
votes
1answer
32 views

Reduction of Circuit Satisfiability to CNFSAT [duplicate]

CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce ...
2
votes
1answer
82 views

Reduce our problem to a known np-complete problem

Subgraph isomorphism We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$. Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ? (i.e. is there a subset of vertices of $G_2, V \subseteq ...
1
vote
1answer
39 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for ...
2
votes
0answers
189 views

PSPACE completeness, with different kinds of reductions [closed]

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
5
votes
1answer
122 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
50 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 ...
0
votes
1answer
52 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 ...
0
votes
0answers
36 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
1
vote
1answer
93 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 ...
0
votes
1answer
212 views

Proving a language is not Turing-recognizable by reduction

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language L is not ...
3
votes
3answers
458 views

The relation between 2SAT and 3SAT

Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P. Or eqivalently - Show that proving 3SAT is in P would prove that 2SAT is NP-Complete. I can see there is an ...
3
votes
2answers
76 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\}$ ...
1
vote
2answers
84 views

If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ? it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea ...
1
vote
2answers
49 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it? Update It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then ...