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

Random searching, write a program that find,search&replace a text string write a program that find,search&replace a text string

Railway reservation system, write an algorithm on railway reservation syste... write an algorithm on railway reservation system

Doubly linked lists-implementation, In any singly linked list, each of the ... In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one d

Asymptotic notation.., important points on asymptotic notation to remember important points on asymptotic notation to remember

Hashing, what is hashing? what are diffrent method of hashing? what is hashing? what are diffrent method of hashing?

Two broad classes of collision resolution techniques, Two broad classes of ... Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Linked list, create aset of ten numbers.then you must divide it into two s... create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Circular doubly link list, what is circular doubly link list?write down the... what is circular doubly link list?write down the algorithm for insertion of elements in circular doubly link list

Define wire-frame model, Define Wire-frame Model This skeletal view is ... Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Implementation of stack, In this unit, we have learned how the stacks are i... In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo