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
Correct Answer: A — Computational complexity
Explanation:
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
Correct Answer: D — Halting problem
Explanation:
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
Correct Answer: B — 2
Explanation:
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
Correct Answer: C — NP complete
Explanation:
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
Correct Answer: B — 2
Explanation:
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
Correct Answer: A — True
Explanation:
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
Correct Answer: B — 2
Explanation:
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
Correct Answer: B — Undecidable problem
Explanation:
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
Correct Answer: A — P class
Explanation:
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)
Correct Answer: D — O(N^2)
Explanation:
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
Correct Answer: C — Undecidable problems
Explanation:
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
Correct Answer: A — NP
Explanation:
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
Correct Answer: A — True
Explanation:
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
Correct Answer: B — Tractable
Explanation:
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))
Correct Answer: A — O(p(n))
Explanation:
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.
