Complexity classes

All decision problems fall in sets of comparable complexity, called as complexity classes.

The complexity class P is the set of decision problems which can be solved through a deterministic machine within polynomial time. This class corresponds to set of difficulty that can be solved effectively in the worst cases. We will consider algorithms associating to this class for analysis of time complexity. Not all of the algorithms in these classes make practical sense as several of them have higher complexity..

The complexity class NP is a set of decision problems which can be solved by a non- deterministic machine within polynomial time. This class contains several problems as Hamiltonian path problem, Boolean satisfiability problem, and the Vertex cover problem.

Posted Date: 4/4/2013 5:39:47 AM | Location : United States

Ask an Expert

Related Discussions:- Complexity classes, Assignment Help, Ask Question on Complexity classes, Get Answer, Expert's Help, Complexity classes Discussions

Write discussion on Complexity classes
Your posts are moderated

Write your message here..

Related Questions

Column major representation, Column Major Representation In memory th... Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

How to improve my 69 algorithm, How can i decrease my latency for 69 moves How can i decrease my latency for 69 moves

Explain worst fit method, Worst Fit method:- In this method the system alw... Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho... The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

Explain the sum of subset problem, a. Explain the sum of subset problem. Ap... a. Explain the sum of subset problem. Apply backtracking to solve the following instance of sum of subset problem: w= (3, 4, 5, 6} and d = 13. Briefly define the method using a sta

Relation of time and space complexities of an algorithm, What is complexity... What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

Explain time complexity, Time Complexity, Big O notation The amount of ... Time Complexity, Big O notation The amount of time needed by an algorithm to run to its completion is referred as time complexity. The asymptotic running time of an algorithm i

Basic datastructures, sample infosys campusconnect questions sample infosys campusconnect questions

Efficient way of storing two symmetric matrices, Explain an efficient way o... Explain an efficient way of storing two symmetric matrices of the same order in memory. A n-square matrix array is said to be symmetric if a[j][k]=a[k][j] for all j and k. For

How can a lock object be called in the transaction, How can a lock object b... How can a lock object be called in the transaction? By calling Enqueue and Dequeue in the transaction.