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

Data mining, hello, i need help in data mining assignment using sas em and... hello, i need help in data mining assignment using sas em and crisp-dm

Explain first - fit method, First - Fit Method: -    The free list is trave... First - Fit Method: -    The free list is traversed sequentially to search the 1st free block whose size is larger than or equal to the amount requested. Once the block is found it

Insertion in list, In the array implementation of lists, elements are store... In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Merge sort , What is the best-case number of comparisons performed by merge... What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke... Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Which sorting methods sorting a list which is almost sorted, Which sorting ... Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Conversion of general trees into the binary trees, By taking an appropriate... By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

Deletion of an element from the linear array, Program will demonstrate dele... Program will demonstrate deletion of an element from the linear array /* declaration of delete_list function */ voiddelete_list(list *, int); /* definition of delete_list

Define about the class invariant, Define about the class invariant A cl... Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

Total impedent of the circuit, an electrical student designed a circuit in... an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program