ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
15 practice sets · Page 1 of 1
The choice of polynomial class has led to the development of an extensive theory called ________
Computational complexity
Time complexity
Problem complexity
Decision complexity
Computational complexity theory seeks to classify problems according to their inherent difficulty based on the resources required to solve them.
Which of the following problems is not NP-complete?
Hamiltonian circuit
Bin packing
Partition problem
Halting problem
Hamiltonian circuit, bin packing, and partition problems are NP-complete. The Halting problem is undecidable — it cannot be solved by any algorithm at all.
How many steps are required to prove that a decision problem is NP-complete?
1
2
3
4
Two steps: first, show the problem is in NP; second, prove that every NP problem is polynomially reducible to it.
To which of the following class does a CNF-satisfiability problem belong?
NP class
P class
NP complete
NP hard
The CNF satisfiability problem belongs to the NP-complete class. It deals with Boolean expressions in conjunctive normal form.
How many conditions have to be met if an NP-complete problem is polynomially reducible?
1
2
3
4
Two conditions must be met: a function t that maps all yes-instances of decision problems D1 to D2, and t must be computable in polynomial time.
A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.
True
False
A non-deterministic algorithm is classified as NP if its verification stage runs in polynomial time.
How many stages of procedure does a non-deterministic algorithm consist of?
1
2
3
4
A non-deterministic algorithm is a two-stage procedure: a guessing stage and a verification stage.
Halting problem is an example for?
Decidable problem
Undecidable problem
Complete problem
Tractable problem
The Halting problem, proved by Alan Turing, cannot be solved by any algorithm and is therefore undecidable.
To which class does the Euler's circuit problem belong?
P class
NP class
Partition class
Complete class
Euler's circuit problem can be solved in polynomial time O(N^2), so it belongs to the P class.
The Euler's circuit problem can be solved in?
O(N)
O(N log N)
O(log N)
O(N^2)
The Euler's circuit problem has a running time of O(N^2).
Problems that cannot be solved by any algorithm are called?
Tractable problems
Intractable problems
Undecidable problems
Decidable problems
Problems that cannot be solved by any algorithm are called undecidable problems. Problems solvable in polynomial time are called tractable.
________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.
NP
P
Hard
Complete
NP (Non-deterministic Polynomial) is the class of decision problems solvable by non-deterministic polynomial algorithms.
The sum and composition of two polynomials are always polynomials.
True
False
One of the fundamental properties of polynomial functions states that both the sum and composition of two polynomials always result in a polynomial.
Problems that can be solved in polynomial time are known as?
Intractable
Tractable
Decision
Complete
Problems solvable in polynomial time are called tractable. Problems that cannot be solved in polynomial time are called intractable.
The worst-case efficiency of solving a problem in polynomial time is?
O(p(n))
O(p(n log n))
O(p(n^2))
O(p(m log n))
The worst-case efficiency of solving a problem in polynomial time is O(p(n)), where p(n) is a polynomial function of the input size n.
