# Tagged Questions

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.

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 ...
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" ?
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!
45 views

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 ...
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$ ...
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 ...
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).
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 ...