305 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 ...
236 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-...
106 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 ...
28 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 ...
994 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 ...
6k 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 ...
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 ...
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 ...
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 ...
1k 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 ...
2k views

### Definition of efficiency versus complexity of algorithm

When I read introductory textbooks I get contradictory answers. In some cases efficiency and complexity are treated the same and the big-O notation is used to indicate that (for example) for an O(n) ...