Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

4
votes
3answers
142 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
5
votes
1answer
200 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
-1
votes
0answers
31 views

Reduction NP-Complete with graph undirected [duplicate]

Given a graph undirected $G=(V,E)$ a subset $I$ of $V$ is indipendent for each couples of vertices u,v in $I$ and {$u,v$} is not in $E$. Prove that the language $L$={$<G,k>$: $k$ is a positive ...
-4
votes
0answers
31 views

Prove that “overlapping edges *through* vertices in a graph” is NP-complete [on hold]

Prove That the problem of recover edges(vertex cover) THROUGH Vertices in a graph determines a language NP -complete . Use it for a Demonstration REDUCTION from the language of the NP -complete ...
18
votes
0answers
354 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, ...
8
votes
3answers
173 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
1
vote
1answer
20 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
0
votes
0answers
38 views

Which of the two properties isn't satisfied?

Show that the following sequence of function $\Phi_n$ is not a measure of complexity: $\Phi_n(x)=\left\{\begin{matrix} \text{ nr of commands } m \text{ that TM } T_n \text{ executes with ...
0
votes
1answer
32 views

Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
2
votes
0answers
19 views

Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
4
votes
1answer
38 views

Constructing languages in NPI other than through Ladner's Theorem

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse ...
3
votes
1answer
251 views

If one-way functions exist are we definitely using them?

I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are ...
1
vote
0answers
59 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
-1
votes
1answer
26 views

What is the relation between differential-privacy mechanism and entropy?

Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy? For example : Laplace distribution that is used to model the noise function ...
5
votes
0answers
59 views

P vs NP and the Time Hierarchy

Assuming P $\neq$ NP, is it possible that there exists a $k$ such that for all $j$, $\textsf{DTIME}(t^j) \subseteq \textsf{NTIME}(t^k)$? There reason I ask is that I assume P = NP implies that for ...
3
votes
1answer
98 views

What is the relation between NC and P/poly?

I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)
8
votes
1answer
1k views

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ...
6
votes
2answers
54 views

Complexity-theoretic difficult of checking the value of $\pi(x)$?

The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$. We can define a decision problem from $\pi(x)$ as follows: Given two numbers ...
1
vote
1answer
42 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 ...
0
votes
0answers
24 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
1
vote
2answers
64 views

NP hard relation with NP complete [duplicate]

If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ? From Theory of computation of ...
-1
votes
1answer
34 views

Why is it true that $NP \ne coNP \implies X = \emptyset$?

Let the class of languages $$X = \{ L \ | \ L\in NPC \land L\in coNPC\}$$ Why is it true that $NP \ne coNP \implies X = \emptyset$?
1
vote
2answers
47 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 ...
2
votes
1answer
31 views

A Query regarding Quadratic Residuocity Problem

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$ x^2\equiv q \pmod{n}. ...
1
vote
0answers
47 views

Calculating Time Complexity of Quadratic Diophantine Equation

The particular quadratic Diophantine equation: $$ R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0 $$ is NP-complete. (a, b, and c are given in their binary representations. a, b, c, ...
2
votes
2answers
68 views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
0
votes
1answer
125 views

Polynominal reduction from unbounded knapsack problem to general integer programming

Given an oracle that can solve in polynominal time: $$a^Tx=b$$ $$x \geq 0$$ So it can solve the feasibility problem with one equality-constraint(a is here a vector and b is a constant, x is required ...
2
votes
0answers
180 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. ...
1
vote
1answer
50 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
3
votes
1answer
125 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
5
votes
1answer
148 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 ...
-1
votes
0answers
27 views

How can I prove that Clique Problem is NP-complete using TSP

I would like to know if there is a way to prove that Clique problem is NP-Complete, using TSP. In order to prove that Clique is NP-Complete, I know that first I have to prove that Clique is NP. Then ...
10
votes
3answers
848 views

Why is the class of NPC important compared to NP-hard?

I'm studying computational complexity and I was wondering why NPC is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard. I also understand ...
9
votes
1answer
1k views

Proving that the conversion from CNF to DNF is NP-Hard

How can I prove that the conversion from CNF to DNF is NP-Hard? I'm not asking for an answer, just some suggestions about how to go about proving it.
1
vote
1answer
15 views

Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$ [duplicate]

For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same ...
4
votes
3answers
133 views

Could an NP-hard problem have a mechanical or physical solution method?

Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we ...
1
vote
2answers
204 views

P vs NP: Assuming P = NP

Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$? I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, ...
3
votes
0answers
38 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)$ ...
0
votes
0answers
30 views

if P=NP then $L\leq L'$ for all languages [duplicate]

How can I prove that if P=NP then for each non-trivial language $L,L'\in NP$ there exists a polynomial reduction $L\leq L'$?
-1
votes
0answers
27 views

reduction from knapsack to 3-SAT

I need a help on how to reduce the knapsack problem to 3-SAT ? I already tried to do it and searched on the net, but I did not find anything.
3
votes
2answers
104 views

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his ...
3
votes
1answer
44 views

Multiple FPT Parameters

The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language. Is there an equivalently defined class that can ...
1
vote
1answer
24 views

(operationalizable) Cost measure for small problems

For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they ...
3
votes
1answer
43 views

Computational complexity of function $U^V$ [duplicate]

Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is ...
14
votes
4answers
812 views

P-Completeness and Parallel Computation

I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is ...
1
vote
1answer
48 views

Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete? [closed]

Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ ...
-2
votes
1answer
44 views

Recursive ,recursively enumerable

I have found this problem- let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , ...
2
votes
1answer
59 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 ...
2
votes
1answer
106 views

Homomorphism erasing information

I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ...
2
votes
2answers
66 views

About a particular use of hashing [closed]

Look at the last problem on page 2 here, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf All one wants to do is to convert a $x \in \{ 0,1\}^n$ into a $y \in \{0,1\}^k$ . Then just a ...