P vs NP

Здравствуйте, nen777w, Вы писали:

Что он доказал равенство или не равенство?

Здравствуйте, UA, Вы писали:

UA>Что он доказал равенство или не равенство? :xz:

Судя по краткому поиску в гуглах/яндексах, доказывать P=NP — его любимое занятие уже лет десять. Регулярно предлагает почти полиномиальные алгоритмы решения NP-полных задач.

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, UA, Вы писали:

UA>>Что он доказал равенство или не равенство?

RO>Судя по краткому поиску в гуглах/яндексах, доказывать P=NP — его любимое занятие уже лет десять. Регулярно предлагает почти полиномиальные алгоритмы решения NP-полных задач.

Слабо верится что они равны, но если это действительно так то

Здравствуйте, UA, Вы писали:

UA>Что он доказал равенство или не равенство?

Статья доступна бесплатно на сайте журнала. Цитата оттуда:

Theorem 4: UF ⊂ NP and UF ≠ NP.
...
Corollary 1: P ⊂ UF and P ≠ NP.
...
Thus, a direct answer to the problem of “P vs NP” consists in the fact that the class P is not equal to the class NP.

Здравствуйте, Manticore, Вы писали:

M>

M>Thus, a direct answer to the problem of “P vs NP” consists in the fact that the class P is not equal to the class NP.

Данное утверждение не имеет смысла до тех пор, пока доказательство не проверят несколько команд специалистов с мировым именем

Здравствуйте, Nuzik, Вы писали:

N>Здравствуйте, Manticore, Вы писали:

M>>

M>>Thus, a direct answer to the problem of “P vs NP” consists in the fact that the class P is not equal to the class NP.

N>Данное утверждение не имеет смысла до тех пор, пока доказательство не проверят несколько команд специалистов с мировым именем

Спасибо, кеп. Я просто на вопрос ответил.

Здравствуйте, UA, Вы писали:

UA>Здравствуйте, nen777w, Вы писали:

UA>Что он доказал равенство или не равенство?

как ни странно — и то, и другое:

2. [Equal]: The 1996 issue (Volume 1, 1996, pp. 16-29) of the "SouthWest Journal of Pure and Applied Mathematics" (SWJPAM) contains the article "Polynomial-Time Partition of a Graph into Cliques" by the Ukrainian mathematician Anatoly Plotnikov. This article designs a polynomial time algorithm for an NP-hard graph problem, and thus proves P=NP.
(SWJPAM is an electronic journal devoted to all aspects of Pure and Applied mathematics, and related topics. Authoritative expository and survey articles on subjects of special interest are also welcomed. SWJPAM serves as an international forum for the publication of high-quality strictly peer-reviewed original research articles. The article is usually sent to at least two experts in the area. Two positive reviews are required for the acceptance and publication of any submitted article.)

...

39. [Equal]: In June 2007, Anatoly D. Plotnikov established P=NP by developping an experimental algorithm for the exact solving of the maximum independent set problem. The theoretical estimation of the running time on n-vertex graphs is O(n^8). The algorithm was tested by a program on random graphs, and the testing confirmed the correctness of the algorithm. The paper "Experimental Algorithm for the Maximum Independent Set Problem" is available at http://arxiv.org/abs/0706.3565.
(Thanks to Mathieu Chapelle for providing this link.)

...

77. [Not equal]: In September/October 2011, Anatoly Plotnikov proved that P is not equal to NP.
The paper "On the relationship between classes P and NP" constructs a class UF that contains P, and that simultaneously is strictly contained in NP; the proof is available at http://arxiv.org/abs/1109.5531. The paper "About set-theoretic properties of one-way functions" provides further analysis of this class UF; it is available at http://arxiv.org/abs/1110.3189.
(Thanks to Igor Razgon for providing these links.)