Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

0
votes
1answer
29 views

How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP. I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N ...
1
vote
1answer
82 views

Why doesn't subset sum solution violate Exponential Time Hypothesis?

The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ...
3
votes
1answer
33 views

Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t ...
2
votes
2answers
116 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 ...
1
vote
1answer
41 views

Problems that are hard in the best case?

Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.
0
votes
1answer
41 views

What is an example for a decidable language not in P?

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?...
0
votes
1answer
29 views

Efficient algorithms for checking non-emptiness of the language of a Turing machine

I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?
3
votes
2answers
88 views

What would NP-complete solution in O(2^N/B) mean?

Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved. So for $B < ...
-1
votes
0answers
22 views

proof that AM[2] contained in NP/poly

can someone help me to prove that AM[2] is contained in NP/poly? I know it's something similar to the proof that BPP contained in P/poly. but I can't figure it out.
-2
votes
1answer
109 views

Show that the complements of NP-languages with one word per length are in NP as well

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs to ...
3
votes
1answer
56 views

Membership problem for context sensitive languages PSPACE-complete

I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself. Let's mark the membership problem for CSL as MEM. First I have to ...
3
votes
6answers
770 views

Is there a meaningful difference between O(1) and O(\log n)?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
3
votes
1answer
26 views

Question regarding Karp-Lipton theorem

In the proof in wikipedia, it goes like this: Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula: $\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$ (where V is polynomial ...
-3
votes
1answer
62 views

proving that pp closed under cook reductions

I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?
-1
votes
1answer
32 views

when can I know if a class (complexity) is closed under reduction (cook/karp)

How do I know if a class let's say PP , is closed under cook reduction or not closed? I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, ...
4
votes
2answers
56 views

Resource bounded reductions for RE-Complete problems

Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this ...
3
votes
2answers
129 views

Proving that PP is closed under symmetric difference

I want to prove that PP is under symmertic difference. let A be a language in PP and B likewise. I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed ...
3
votes
1answer
107 views

Meaning behind 1/ϵ in FPTAS

I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS. A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme ...
-1
votes
1answer
26 views

Poly-time reduction from HAMPATH to HAMPATH-E

I need to prove that HAMPATH-e = { < G,s,t,e > | G is directed graph, s, t are vertices and e a edge } there is hamiltonian path between s to t that cross the edge e is an NP complete. i've ...
2
votes
1answer
30 views

What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
2
votes
0answers
76 views

Practical implications of strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?
5
votes
3answers
105 views

Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?

I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063: ...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!...
1
vote
2answers
39 views

Oracle Relations Between Complexity Classes

I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally ...
2
votes
0answers
22 views

Quantum circuits for multiplication

Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. Using that algorithm, combined with uncomputing, you can make a ...
1
vote
1answer
44 views

Small hard 3-SAT instances

I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4. However, I would like to know ...
0
votes
1answer
16 views

Bin packing with given bin sizes, not necessarily same

I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP ...
4
votes
0answers
41 views

Cloning the output of a quantum program with unknown input but known measurements

Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to ...
-4
votes
0answers
18 views

Reductions between CNF-SAT and DNF-SAT

Can someone help me to prove or disprove the following three claims about reductions between CNF-SAT And DNF-SAT? There is polynomial reduction from CNF-SAT to DNF-SAT. There is polynomial reduction ...
11
votes
2answers
360 views

Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked ...
8
votes
1answer
178 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
2
votes
2answers
73 views

What are the hardest problems that are in P if and only if P=NP?

I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are ...
3
votes
1answer
73 views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
3
votes
1answer
62 views

Why is Knapsack and ILP NP-complete

I have a question concerning several NP-hard problems and why they are (or are not NP-complete). I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and ...
-1
votes
1answer
49 views

Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem: $$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$ to a problem, where i have a matrix ...
6
votes
1answer
107 views

Are there any known lower-bounds for complexity on Non-determinsitic machines

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time. Are they any problems where we have known lower bounds for ...
1
vote
1answer
98 views

Prove or disprove that DTIME(n^2)=NL

I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\...
-1
votes
2answers
66 views

What is the simplest known NP-Complete problem for testing P=NP solutions? [closed]

About a year and a half ago I ask this question regarding $P=NP$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic. With that stated, ...
1
vote
2answers
135 views

Scheduling a sequence of queue operations that push and pop items at specified times

What is the time complexity of the following problem? Definitions A FIFO is a queue functional unit with the commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of ...
4
votes
3answers
2k views

Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

Basic sanity check on NP-complete solutions: Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively ...
1
vote
1answer
33 views

Can QBF encode #QBF?

In another question Initializing non-deterministic variables in QBF, I was interested about translating assertion-based pseudocode to QBF in order to have an exponentially more compact encoding ...
1
vote
1answer
226 views

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in ...
147
votes
6answers
61k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
0
votes
0answers
18 views

what is NP class? [duplicate]

I actually started to read complexity classes of problems. and I know that NP class include P class problems and even more problems call NP-complete ... as many books define NP class as well But I ...
0
votes
1answer
33 views

Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
1
vote
1answer
18 views

Example Turing Machine for a time-constructible function

I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a ...