Tagged Questions

Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

-2
votes
0answers
19 views

how to reduce 3-colorable graph to this?

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best to reduce to ...
0
votes
1answer
28 views

Time Complexity of Queue Problem

What is the time complexity of the following problem? Definitions Given a discrete time axis, define a FIFO as a queue unit with the commands: PUSH (data to back of queue), POP (the head of the ...
1
vote
0answers
20 views

Minimal polynomial reduction of dominating set to max clique

Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$ It is well known that it is NP ...
1
vote
1answer
52 views

What complexity class is this ciruit problem?

I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds. Without knowing the runtime, I speculate on how quickly it will ...
0
votes
3answers
56 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
-3
votes
0answers
14 views

Threshold Circuits of Bounded Depth [on hold]

I'm reading an article on circuit complexity and I want to know how to prove the theorem about $\mathrm{TC}^2$ vs $\mathrm{TC}^3$.
5
votes
0answers
35 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 ...
1
vote
1answer
35 views

Karp reduction from 3-SAT to 3-PARTITION

I want to show that this problem is NP-complete: partition a set of 3n real numbers to n partitions of 3 number which each partition has the same sum of its members. I want to reduce 3-SAT to this ...
-1
votes
1answer
22 views

polynomial time reduction of 2 langauges

If we can reduce a language y to x. x ≤P y how do I prove x(complement) ≤P y (complement)
-1
votes
1answer
36 views

What is a CNF Satisfiability [on hold]

I am trying to understand the concept of CNF satisfiability, can someone throw some light on 1) what does 3- CNF, 4- CNF etc.. mean? 2) What does yes and no instance mean and can someone provide an ...
2
votes
0answers
75 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, ...
2
votes
1answer
21 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
2
votes
2answers
44 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
8
votes
1answer
249 views

Is there an efficient algorithm for expression equivalence?

e.g. $xy+x+y=x+y(x+1)$ ? The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or ...
1
vote
1answer
152 views

Concatenation of languages in NP

I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my ...
5
votes
3answers
301 views

3SAT analogous problem in P

Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P? For instance if we solve this problem in P, may be we can solve prime ...
2
votes
1answer
66 views

Are there any coP problems

Is there a notion of coP problem? Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
0
votes
1answer
55 views

If P = NP, then is NP = FNP?

I read FP = FNP iff P = NP which makes sense. But if P = NP, does it mean FNP = NP? Intuitively, I think no because P = NP would mean that decision problems in NP would become decision ...
2
votes
1answer
32 views

Property of two ANEAs is in NP

I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A_1}$ and $\mathcal{A_2}$ and want to show that the problem $L(\mathcal{A_1}) \not \subseteq L(\mathcal{A_2})$ is in NP by ...
4
votes
1answer
26 views

Is complexity of $GI_{di}$ same as $GI_{un}$?

Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)? It is clear $$GI_{un}\leq GI_{di}$$ since the set of ...
3
votes
1answer
44 views

What is the Certificate for Set Cover?

Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, ...
-1
votes
1answer
27 views

Solving a Variation of knapsack [closed]

I'm working on a problem which to me, seems very similar to a knapsack problem: A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ...
3
votes
2answers
91 views

What's the big deal with the knapsack problem?

In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic ...
0
votes
1answer
33 views

Time complexity for two multiplications modulo $p$

The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$. What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?
3
votes
3answers
134 views

Shouldn't complexity theory consider the time taken for different operations?

I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison. I am trying to understand why each basic operation ...
4
votes
1answer
50 views

Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Assuming $\Sigma = \{ 0, 1\}$.. Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$? So it ...
0
votes
1answer
18 views

Is Bin-Packing with only 2 types of objects polynomial?

Is the following problem polynomial ? Or NP-Complete ? Problem: Bin packing with 2 types of objects. Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ ...
0
votes
2answers
53 views

How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?

Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at ...
0
votes
1answer
40 views

Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests?

Since you are free to chose any formula for the SAT problem, doesn't the choice of a formula that requires a test for each subset of the group of variables force it to perform $2^N$, essentially ...
1
vote
2answers
43 views

Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help. The Weighted Maximum Coverage problem is ...
1
vote
1answer
26 views

Is the maximum coverage variant of Vertex Cover also NP-hard?

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible ...
2
votes
1answer
52 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
0
votes
2answers
62 views

What is the definition of a problem

In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem? How specific should a problem be? For example, can the followings all ...
1
vote
1answer
31 views

Generating all factorials up to $n$: faster than naive approach?

I'm aware of prime decomposition and parallel approaches to calculating one factorial; however, if I want the factorials of all numbers up to $n$, is there anything more efficient than the naive ...
0
votes
0answers
16 views

TSP cycle approximation proofs

Having a hard time formulating the proof for this. The professor kinda breezed through the problems and I just want an explanation on how best to tackle this and how one would prove what it's ...
1
vote
2answers
50 views

A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
4
votes
2answers
55 views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
0
votes
0answers
32 views

Tip Jar splitting problem [duplicate]

Having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete. In all of these situations the input is a "tip jar" ...
2
votes
0answers
60 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\}$, ...
2
votes
1answer
47 views

Is ecological bin packing NP-hard?

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as: Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, ...
2
votes
1answer
47 views

Acyclic Graph in NL

From the book The Nature of Computation by Moore and Mertens, exercise 8.9: Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and ...
1
vote
1answer
65 views

When is splitting a collection coins two ways NP-complete?

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ...
3
votes
0answers
45 views

Natural language processing complexity

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the [natural-lang-processing] and [complexity-theory] tags (and related complexity tags), but have not turned up ...
0
votes
1answer
34 views

Need help to derive the Complexity!

Please help me regarding this one! What will be the communication and computation complexity of this code?? ...
4
votes
3answers
55 views

When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
-2
votes
0answers
23 views

Draw out TM where 1<=n<=|w| the nth character from the left is equal to the nth character from right

We need to write TM for strings over {a,b,c} for some n, 1<=n<=|w| the nth character from the left is equal to the nth character from right. Can someone help me understand the meaning and how ...
3
votes
2answers
258 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
3
votes
1answer
47 views

What if $NP\subseteq BPP$?

I'm new to complexity and came upon the following exercise which I'm unable to solve. Prove that if $NP\subseteq BPP$ then $\Sigma_2^p=\Pi_4 ^p$.
6
votes
3answers
233 views

What problem cannot be solved by a short program?

BACKGROUND: Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of ...
1
vote
0answers
62 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...