# Is protein folding really NP-hard and how to show that?

This question has two facets that are related.

Is the general problem of protein folding really NP-hard?

The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a lattice (similar to self-avoiding walk):

Simplification significantly reduces the computational effort in handling the model, although even in this simplified scenario the protein folding problem is NP-complete.

However, this simplification takes a continuous problem which has some local convexity characteristics in real life into an integer programming problem, because protein folding resembles the problem of finding the global minimum on some continuous energy "cost function", also known as the energy landscape as illustrated by Ken Dill et al., 2012:

As stated by others, translating a problem defined over continuous domain into problems over the integers or a binary lattice may introduce higher complexity cost. You may think about it as taking a linear problem and solve it using 3SAT solver, any problem in $$P$$ is presumably reducible to 3SAT. I assume that there is a convex nature to the energy landscape, and this piecewise convexity is beneficial for the search for the minimal energy state.

How to reduce hydrophobic-polar protein folding to TSP/3SAT/CNF?

The work by Bahi et al. really confused me. I expected it to be something relatively simple to reduce 3SAT or TSP to the problem of protein lattice, because intuitively it seems that finding Hamiltonian path could be stated as finding a protein conformation on a lattice.

Bahi, Jacques M., et al. Computational investigations of folded self-avoiding walks related to protein folding. Computational biology and chemistry 47 (2013): 246-256.

Bahi, Jacques M., et al. Chaos of protein folding. In IJCNN 2011, Int. Joint Conf. on Neural Networks, pages 1948–1954, San Jose, California, United States, July 2011.

Bahi, Jacques M., et al. Protein folding in the 2D hydrophobic-hydrophilic (HP) square lattice model is chaotic. Cognitive Computation, 4(1):98–114, 2012.

Bahi, Jacques M., et al. Is protein folding problem really a NP-complete one ? First investigations. arXiv:1306.1372, October 2012. Submitted to Journal of Bioinformatics and Computational Biology (Elsevier).

Bahi, Jacques M., et al. Unfoldable self-avoiding walks are infinite. Consequences for the protein structure prediction problem. arXiv.org, 2013.

Bahi, Jacques M., et al. Protein structure prediction software generate two different sets of conformations. Or the study of unfolded self-avoiding walks. arXiv:1306.1439, 2013.

• Not all simple to state problems have simple to state solutions. It is common for a simple-to-state theorem to have a complex proof.
– D.W.
Jul 18 '20 at 18:06
• @D.W. True, I am aiming to have the outline of a potential proof. $x^n+y^n=z^n$
– 0x90
Jul 18 '20 at 18:10
• But don't papers in the literature already contain a proof that protein folding is NP hard? You can find citations to such papers in the ones you cited. It seems like they answer your first question.
– D.W.
Jul 18 '20 at 19:24