209 views

### what is the difference between “language” and “certificate” in complexity theory? [duplicate]

Seems like they both are set of strings for which the problem returns "yes" in decision problems. P class is consists of problems so we can only say a problem is in P. But we sometimes say that a ...
160 views

### How does “language” relate to “problem” in complexity theory? [duplicate]

I am looking up the meaning of reduction in complexity theory: On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem On the Princeton's notes on NP-...
102 views

### The defining property of problems in NP [duplicate]

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
26 views

### Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?
26 views

### Between languages and problems [duplicate]

I have a pretty good handle on what recursive and recursively enume table languages mean with respect to Turing machines and how they relate to one another through my algorithms class. What I don't ...
929 views

### Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
4k views

### Why is the halting problem semi-decidable?

This is what is know about halting problem and semi-decidability :- Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x. A ...
5k views

### Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
3k views

### Time complexity of Ackermann's Function

How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann ...
5k views

### If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
2k views

### Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
920 views

### Is O(ln n) “exponentially faster” than O(n)?

I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear ...
518 views

### Complexity analysis of an unsolvable algorithmic problem?

In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned ...