Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

0
votes
0answers
6 views

approximate algorithm #P RP with NP oracle PH

I need to proof - that if to all f that is #P there is TM with probabilty: Pr[f(x)/5 < M(x,r) < 5 * f(x)] > 1-1/3(|x|) so - PH=NP^RP. from that I can know that the Probabilistic ...
0
votes
0answers
11 views

Runtime complexity of TextRank

I am reading a paper [1] about the TextRank algorithm in keyword extraction and they mention the recursive formula: $$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \; \in \; In(V_{i})} \frac{...
0
votes
1answer
16 views

Checking membership in DFA with fixed length using AC1 circuit?

I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
2
votes
0answers
22 views

Oblivious Universal Turing Machine in O(T log(T)) time

I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
1
vote
1answer
93 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
35 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 ...
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$ ?...
1
vote
1answer
43 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.
1
vote
2answers
48 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?
-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.
3
votes
2answers
96 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 < ...
-3
votes
1answer
63 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?
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 ...
-1
votes
1answer
37 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, ...
3
votes
2answers
141 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
108 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 ...
5
votes
3answers
109 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}!...
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 ...
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 ...
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 ...
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 ...
-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 ...
2
votes
2answers
75 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
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
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
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\...
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
34 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 ...
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 ...
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
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 ...
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 ...
3
votes
1answer
40 views

Sipser exercise : variant of CNF is NL-complete

I'm stuck rather badly on a Sipser exercise, 8.21 in my edition: 8.21 Let $CNF_{H1}$ = {<$\phi$> | $\phi$ is a satisfiable cnf-formula where each clause contains any number of positive literals ...
-1
votes
1answer
52 views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a turing machine but I got stuck with the thing of ...
1
vote
0answers
42 views

Why do we need cook reductions?

I have a question about cook reductions and karp reductions. Which is the stronger form? As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp ...
1
vote
1answer
40 views

Trouble seeing the contradiction in diagonalization proof

I've seen the proof on a pdf online, and I'm having trouble seeing the contradiction. If $(\langle T\rangle,z)=w \in D$, so when we emulate $T(w)$ with $U$ (universal machine), it accepts within the ...
-1
votes
0answers
49 views

Prove that if X is in NP and Y reduces to X, then Y is also in NP

Prove that if X ∈ NP and Y ≤p X, then Y ∈ NP I'm having so trouble with how to go about this proof. I think the steps are to say that X is in NP, and Y reduces to X, therefore if we can solve X, we ...
0
votes
1answer
20 views

How do I show this variant of the longest path problem is NP-hard?

The problem is as follows: "Given a weighted graph G and a path p, show that p is the longest simple path in G." I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my ...
5
votes
2answers
303 views

Is this an instance of a well-known problem?

Context I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I ...
2
votes
2answers
97 views

How are games like chess provably harder than NP?

From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ...
0
votes
0answers
25 views

If problems P1 and P2 are known to be NP-hard, then we can conclude that P1∝P2 and P2∝P1? [duplicate]

I know the definition of NP-hard is that “a problem(P1 or P2) is NP-hard if every NP problem could be polynomially reduce to (P1 or P2)”. However, P1∝P2 means P1 could be polynomially reduced to P2, ...
3
votes
2answers
325 views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
3
votes
1answer
33 views

How does (non)deterministic time relate to verifiability?

So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It ...
4
votes
1answer
79 views

Does P=NP imply polynomial solutions to #P?

Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so ...
5
votes
1answer
182 views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
0
votes
0answers
18 views

Complexity of Self avoiding walks in unary

In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and ...
4
votes
2answers
52 views

How do you prove that polynomial reductions are not symmetric?

How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other ...