To prove P = NP, it is not enough to find an NP problem that can be solved in polynomial time, but you need an NP-complete problem that can be solved in polynomial time. The problem P != NP is maybe more complicated.

Paul Erdős said: if extra-terrestrial people are saying that if we do not prove that P = NP or P != NP in a year, they are going to launch a war against the Earth, then it is not the good solution for all mathematicians to work on this problem, but to prepare for the war.

To prove P = NP, it is not enough to find an NP problem that can be solved in polynomial time, but you need an NP-complete problem that can be solved in polynomial time. The problem P != NP is maybe more complicated.

Paul Erdős said: if extra-terrestrial people are saying that if we do not prove that P = NP or P != NP in a year, they are going to launch a war against the Earth, then it is not the good solution for all mathematicians to work on this problem, but to prepare for the war.

You need to familiarize yourself with complexity classes and separation of classes. To show equality you need a problem that any other problem in the class can be translated to this problem (efficiently in poly time), namely the entire class is reduced from it and solve it in POLYNOMIAL TIME (Such a problem is known to be "an NP-hard problem", it is as hard as any other problem in NP-- does not need to be [but can be] NP-complete and to have a solution in the class NP itself since you just show it is in P thus in NP). For separation NP P, one needs to exhibit a separation: like taking a problem as above (say NP-complete) and show that it requires non-polynomial-time resources, directly. Or use indirect methods that separate classes like obviously any problem in P is also in NP, so if one can show that NP contains more languages in some way there is a separation, etc.

BUT: the state of the art of lower bound techniques and other separation methods is such that we have very little knowledge (or: no knowledge, in fact) on how to approach this separation........

Some basic reading: https://en.wikipedia.org/wiki/Complexity_class

It would not be my suggestion that you ry this as your starting research project, but knowledge about complexity classes (and I spoke loosely above about them) is very fundamental to understanding of computation and computational resources....

You think of what NPC problem could be solved in polynomial time, and then provide the solution. But as Zoltan Kasa put it, it is by far more complex to accomplish than might look like.

Eu também estou estudando alguns problemas NP e tentando encontrar uma solução P. Particularmente na área de Linguagens Formais, começando com coisas simples, como por exemplo transformar uma expressão regular num automato finito.

Também estou tentando encontrar um caminho de forma P para resolver o Problema da Parada (relaciono com o "problema entschuldigung"). Neste caso, algumas manipulações NP que estão na literatura para resolver algumas partes, estou tentando um algorítmo de forma P. Uma solução que já consegui foi o algoritmo para a detecção de laços infinitos.

Na verdade, este meu relato tem como objetivo de trocar informações com pessoas que estão estudando este assunto a fundo.

As soluções que tenho conseguido são dentro de uma visão computacional, e não matemática (o que acho nada agradável!).

The previous translation the text was impaired. Because of this, I am putting the text back into English.

I am also studying some NP problems and trying to find a solution P. Particularly in the area of Formal Languages, starting with simple things, such as transforming a regular expression into a finite automata.

I am also trying to find a way of P to solve the Stop Problem (related to the "entschuldigung problem"). In this case, some NP manipulations that are in the literature to solve some parts, I'm trying a P-form algorithm. One solution I already managed was the algorithm for detecting infinity.

In fact, my account is meant to exchange information with people who are studying this subject in depth.

The solutions that I have achieved are within a computational view, not mathematical (which I find nothing pleasant!).

I recommend this (kinda long) review from Scott Aaronson as it's probably the most comprehensive article on this topic:

http://www.scottaaronson.com/papers/pnp.pdf

Announcement blogpost with kindle friendly links and other stuff:

https://www.scottaaronson.com/blog/?p=3095

Jose, when you've finished with the halting problem, let me know, because I have a program that calls it as a subroutine.

Peter!

I do not know yet if I will achieve my final goal. I think the theoretical part is well advanced. The implementation (which I consider a more technical part) is still lacking.

So far I've created an algorithm to turn monolithic programs into compound labeled instructions (not using the flowchart scheme). From the compound labeled instructions I detect the infinite loops.

After that I created a Virtual Machine Label (MVR) based on the "Norma" machine proposed by Richard Bird, and the MVR is not iterative but monolithic. It also only works with natural numbers and has only one test. This single test was what led the algorithm to be P.

High-level language programs are converted to the MVR. The object program (for the MVR) gets a little larger (with respect to the number of instructions - because as there is only one test statement - if memory equals 0, before testing I have to throw the specific memory to the test register) .

I tried to explain in a very general way the path I'm researching, and with a computational and non-mathematical vision. I inform you that my mathematical knowledge is weak.

I hope you're not being silly! rssss