Use for algorithms, algorithm-analysis and complexity-theory questions that aim for polynomial running time resp. time complexity. Such questions often are are reference-requests or about runtime-analysis or time-complexity.

learn more… | top users | synonyms

-1
votes
0answers
23 views

Prove that all P problems except {} and {a,b}* are complete [duplicate]

It is easy to say that {} and {a,b}* are not P complete because other problems in P can't be reduced to these because ...
0
votes
0answers
49 views

Polynomial Reduction and P [duplicate]

Why w ∈ A if and only if f(w) ∈ B ? Which the signification of "if and only if" ?
-1
votes
0answers
8 views

Polynomial time reduction Hampath to TSP [duplicate]

Is there a polynomial time reduction from Hamiltonian Path to TSP (travelling salesman problem)? If so, could you tell me? Thank you in advance!
0
votes
1answer
45 views

If the Clique-k Problem is in P, why not Clique as well?

I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?) The general clique problem is defined as $\text{CLIQUE} = \left\{ (G, k) | ...
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
45 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$ ?...
2
votes
1answer
49 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
4
votes
2answers
57 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 ...
0
votes
0answers
30 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
-1
votes
1answer
54 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 ...
0
votes
0answers
26 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, ...
5
votes
1answer
85 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
183 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 ...
2
votes
1answer
63 views

Why is the set of perfect squares in P?

I am reading an article by Cook [1]. In it he writes: The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots. I can see how to use Newton's ...
6
votes
1answer
3k views

Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document [1]. The following is my attempt to answer the question. Assume that we design a ...
-1
votes
1answer
36 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
4
votes
1answer
41 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\...
1
vote
2answers
68 views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
4
votes
2answers
64 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
0
votes
1answer
10 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
2
votes
1answer
26 views

On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
4
votes
2answers
85 views

Implicit complexity and interpretation of total languages

In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be ...
2
votes
1answer
127 views

Polynomial hierarchy: inclusion between spaces

Using the definition for the polynomial hierarchy: $$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$ $$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$ I have been asked to to show that: $$ P^{\Pi_k^P } \subseteq \Pi_{k+1}...
1
vote
1answer
38 views

If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time? Problem ...
-1
votes
1answer
43 views

A program for polytime languages

Does their exist a program P[m,s] which always halts and for any polytime language exists an m; possibly incomputable; such that P[m,s] accepts only those strings s which are in the language.
4
votes
1answer
46 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
7
votes
3answers
216 views

Why are most (or all?) polynomial time algorithms practical?

I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{...
8
votes
3answers
286 views

Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
10
votes
2answers
343 views

Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
-1
votes
1answer
34 views

P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
0
votes
0answers
21 views

Pedagogic reference on cut generating functions

Can you recommend an introduction to the topic of cut generating functions? I am looking for introductory or review-like material. I did find the following survey paper, but it seems to be addressed ...
4
votes
2answers
508 views

Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. ...
5
votes
1answer
552 views

Can we show that non-determinism adds no power, for some specific running time?

$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$ $P = \cup_{k \in \mathbb{N}} TIME(n^k)$ Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$? For how large of a $k$ can we show the above ...
1
vote
0answers
26 views

Besides practical computing applications, is there a reason polynomial is “good” and exponential is “bad”? [duplicate]

The overarching theme of computer science seems to be that polynomial time or space or what-have-you for an algorithm is a success, and exponential is a failure. The definitions of P and NP revolve ...
10
votes
1answer
138 views

If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability". Any algorithm whose time complexity function cannot be so bounded is called an exponential time ...
4
votes
1answer
59 views

Machine with an oracle for a language that cannot decide another language in polynomial time

We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$. However, there is any explicit ...
0
votes
0answers
21 views

How to prove an algorithm with subroutines to belong to the polynomial time category using correct notation? [duplicate]

I'm having some trouble with writing my answer with the correct notation. I suppose I get the basic idea how to solve this and wrote down my answer but my gut tells me that that it's not ...
3
votes
1answer
55 views

Do poly-time algorithms exist whose time complexity is unprovable?

If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?
2
votes
1answer
48 views

Can one find the minima of a convex function efficiently?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$. Is there any $poly(n)$ algorithm that for any class ...
11
votes
1answer
325 views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
9
votes
2answers
712 views

Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
1
vote
1answer
78 views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
2
votes
0answers
30 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 ...
1
vote
0answers
62 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?
8
votes
0answers
120 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 ...
6
votes
3answers
203 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
1
vote
0answers
24 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
3
votes
1answer
308 views

What is the decidable language in $P/poly$ but not in $P$?

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
3
votes
1answer
53 views

Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?

It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using Tseitin transformation: $$ Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \Phi \Rightarrow Q_1 ...
4
votes
2answers
248 views

Why is it important to solve a problem in Polynomial time, In cryptography?

I have just started to learn Cryptography. I am trying to learn "Merkle-Hellman Knapsack Cryptosystem". So, right at the beginning of the discussion, a question came in my mind: Why is it important ...