Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

9
votes
1answer
303 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 ...
5
votes
3answers
86 views

Complexity of natural language processing problems

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 any ...
0
votes
0answers
24 views

Need help classifying this problem and suggestions on how to tackle it

I've got an idea for a tool I want to make but I am not sure how to go on about trying to solve it... I was hoping if you could help me classify it and also give me some suggestions on how I could try ...
1
vote
1answer
76 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 ...
1
vote
1answer
25 views

Diophantine equations and P=NP

It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates ...
9
votes
1answer
142 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor ...
0
votes
1answer
52 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 ...
0
votes
1answer
21 views

Extended knapsack: is it NP-complete?

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot ...
3
votes
1answer
38 views

PARTITION with 0-sum assumption

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete. My question: does the partition problem remain ...
1
vote
1answer
171 views

Subset sum algorithm in O(n³ log n)?

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ...
0
votes
3answers
141 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
3
votes
1answer
68 views

Question regarding Cook-Levin theorem proof

I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing ...
1
vote
1answer
50 views

How to prove that this is NP complete?

I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete. I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete ...
0
votes
1answer
39 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
1
vote
1answer
177 views

Show there exists a turing machine with the following properties

I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the ...
1
vote
0answers
18 views

Information content of computational problems

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal ...
4
votes
0answers
64 views
+100

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 ...
10
votes
2answers
163 views

Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was. Can you solve the following problem in polynomial time or is ...
-3
votes
0answers
27 views

how to reduce 3-colorable graph to this? [on hold]

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
3answers
64 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 ...
1
vote
1answer
62 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 ...
5
votes
0answers
50 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 ...
-3
votes
0answers
14 views

Threshold Circuits of Bounded Depth [closed]

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$.
1
vote
1answer
39 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
23 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)
2
votes
0answers
83 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, ...
-1
votes
1answer
38 views

What is a CNF Satisfiability [closed]

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 ...
13
votes
5answers
1k views

How to prove a problem is NOT NP-Complete?

Is there any general technique for proving a problem NOT being NP-Complete? I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of ...
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 ...
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 ...
2
votes
2answers
46 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$. ...
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 ...
2
votes
1answer
74 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)?
5
votes
3answers
306 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 ...
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
27 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
30 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)$?
1
vote
2answers
45 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 ...
3
votes
3answers
139 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 ...
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
54 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
41 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 ...
2
votes
1answer
54 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 ...
1
vote
1answer
30 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 ...
0
votes
2answers
64 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 ...