Linked Questions

0
votes
1answer
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 ...
1
vote
1answer
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-...
0
votes
0answers
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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
10
votes
3answers
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 ...
7
votes
1answer
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 ...
13
votes
2answers
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 ...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
4
votes
2answers
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 ...
3
votes
1answer
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 ...
1
vote
4answers
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 ...
4
votes
2answers
1k 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) ...
1
vote
2answers
320 views

How does an automaton model a computer or something else?

An automaton, as I have seen so far, is used to tell if a string belongs to the language that the automaton recognizes. This is determined by the final state of the automaton running on the string as ...

15 30 50 per page