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
So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part