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

Two sparce matrices multipilcation algorithm, Write an algorithm for multi... Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Algorithm.., write an algorithm to sort given numbers in ascending order us... write an algorithm to sort given numbers in ascending order using bubble sort

Types of a linked list, A linked list can be of the following types:- ... A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

Hash function, Q. Define the graph, adjacency matrix, adjacency list, hash ... Q. Define the graph, adjacency matrix, adjacency list, hash function, adjacency matrix, sparse matrix, reachability matrix.

Array, extra key inserted at end of array is called extra key inserted at end of array is called

Infix expression into the postfix expression, Q. Convert the given infix ex... Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix

Queues, Queue is a linear data structure utilized in several applications o... Queue is a linear data structure utilized in several applications of computer science. Such as people stand in a queue to get a specific service, several processes will wait in a q

Link list, algorithm for multiplication of two sparse matrices using link l... algorithm for multiplication of two sparse matrices using link list

[plkm, ` `

Function performs multiplication of two numbers, You need to write a functi... You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl