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

Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi... 1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

Travelling sales person, explanation with algorithm explanation with algorithm

Usage of linked lists for polynomial manipulation, Q. Establish the usage o... Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Program on radix sort., Write a program that uses the radix sort to sort 10... Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Entity relationship, what is cardinality what is cardinality

Creation of Heap, Q. Create a heap with the given list of keys: ... Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation

Algo for quicksort, Easy algorithm for beginner for quicksort with explanat... Easy algorithm for beginner for quicksort with explanation

Traversing a graph, two standards ways of traversing a graph in data struc... two standards ways of traversing a graph in data structure

How to construct binary tree, Q. A Binary tree comprises 9 nodes. The preor... Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

Algorithm, what algorithms can i use for the above title in my project desi... what algorithms can i use for the above title in my project desing and implmentation of road transport booking system