Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based...

Area of Science:

• Computer Science
• Biotechnology
• Computational Complexity Theory

Background:

• Cook's Theorem establishes that an algorithm for one NP-complete or NP-hard problem can solve others via reduction.
• The theorem's validity has been confirmed on conventional digital computers.
• DNA computing offers a novel paradigm for addressing complex computational problems.

Purpose of the Study:

• To propose a DNA algorithm for solving the vertex-cover problem, a known NP-complete problem.
• To validate Cook's Theorem within the context of DNA-based computing.
• To explore the applicability of the proposed DNA algorithm to other NP-complete and NP-hard problems.

Main Methods:

• Development of a novel DNA algorithm specifically designed for the vertex-cover problem.
• Analysis of problem size reduction for applying the vertex-cover DNA algorithm to other NP-complete/NP-hard problems.
• Comparative assessment of DNA algorithm performance against theoretical computational models.

Main Results:

• A functional DNA algorithm for the vertex-cover problem was successfully developed.
• It was demonstrated that Cook's Theorem holds true for DNA computing when problem sizes are comparable or smaller.
• The study confirms the direct applicability of the proposed DNA algorithm for solving reducible NP-hard problems.

Conclusions:

• The proposed DNA algorithm effectively solves the vertex-cover problem, supporting Cook's Theorem in DNA computing.
• For NP-hard problems not directly reducible or larger than vertex cover, tailored DNA algorithms may be necessary.
• This research bridges computational complexity theory and DNA computing, opening avenues for new algorithmic solutions.