Of course I don't have a mathematical proof that P = NP cures cancer. Nor would an efficient algorithm for SAT immediately give a cancer cure. But it could work as follows:

- We need an appropriately shaped protein that would inhibit the cancer cells for a specific individual without harming the healthy cells. P = NP would help find these shapes perhaps just the DNA of the person and the type of cancer.
- At this point we don't understand the process that takes a ACGT protein sequence and describes that shape that it forms. But it must be a simple process because it happens quickly. So we can use P = NP to find a small circuit that describes this process.
- Use P = NP to find the protein sequence that the circuit from #2 will output the shape from #1.

^{50}algorithm for SAT won't do the job. All this steps may happen whether or not P = NP but we'll need some new smart algorithmic ideas.

Please note this is just a thought exercise since I strongly believe that P ≠ NP. I do not want to give false hope to those with friends and loved ones with the disease. If you want to cure cancer your first step should not be "Prove P = NP".

Ill-informed articles such as this one are the reason why Trump got elected.

ReplyDeleteWhy is it ill-informed? Elaborate ...

ReplyDeleten-body simulation is PSPACE-complete and thus no guarantee that P=NP (even a linear time algorithm) would mean we can simulate the folding of proteins quickly (https://en.wikipedia.org/wiki/N-body_simulation#Computational_complexity).

ReplyDeleteAnd even if we could, no guarantee that we can actually so precisely target cancer cells using just proteins in the first place.

So we keep mentioning the efficiency of the algorithm in terms of the input size (n), but what defines (n) for SAT ? Is it the number of clauses ? Is is the number of total variables ? Which one of them ?

ReplyDeleteAs with most decision problems, complexity for SAT is conventionally measured in terms of the length of the input. This is roughly O(clauses * log(variables)). Some authors use 'n' for the number of variables though, so in actual papers you want to check the definitions. It rarely matters in casual contexts, since SAT problems with very low or very high clause/variable ratios are generally easy.

DeleteTy, that really helped.

DeleteThis article sounds just about as ridiculous to biologists as it does to quantum computing folks when people with no background talk about their field...

ReplyDeleteYou could see my proof of UP=NP in

ReplyDeletehttps://www.academia.edu/37430336/UP_versus_NP

and see my proof of P = NP in

https://www.academia.edu/37431232/Sparse_complete_sets_for_coNP_Solution_of_the_P_versus_NP_problem

You could download them in Zenodo in the respective url:

For UP=NP, we have

https://zenodo.org/record/1419750#.W55I5xnB8ew

For P=NP, we have

https://zenodo.org/record/1420486#.W5_TC9JKjIU

In general, you could see my whole research in

https://uh-cu.academia.edu/FrankVega

Thanks in advance....

How many variables are in those problems?

ReplyDelete(We do have kind of efficient SAT solvers.

But don't we need NP=LIN to handle those bio problems?)

So according to Ryan Williams on Twitter SAT ist solvable now, but the next level of the PH requires exponential time. I guess this is not proven, just a new ETH. History might repeat itself, and maybe in 15 years Sigma2 SAT is solvable in practice and cancer will be cured after all.

ReplyDelete