Complexity classes, Data Structure & Algorithms

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







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
Related Questions
A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Question

1. What is an expert system and where are they needed? 2. What are the major issues involved in building an expert system?


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

Illustrates the program for Binary Search. Program: Binary Search /*Header Files*/ #include #include /*Functions*/ void binary_search(int array[ ], int value,

Multilist Representation of graph