Historical dossier 003

An algorithm with polynomial time complexity for finding clique in a graph; HEWN: A polynomial algorithm for CLIQUE problem

A recorded P = NP claim by Tang Pushan, Huang Zhijun, preserved from Woeginger’s frozen 2016 page.

Dossier: 003
Author(s): Tang Pushan, Huang Zhijun
Date recorded: Around 1997; 1998
Direction: P = NP
Works or versions: 3
Adjudication: Recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(3)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: Around 1997 Tang Pushan provided a polynomial algorithm for the clique problem. The two relevant papers are "An algorithm with polynomial time complexity for finding clique in a graph" by Tang Pushan (Proceedings of 5th International Conference on CAD&CG;, Shenzhen, P.R. China, 1997, pp 500-505) and "HEWN: A polynomial algorithm for CLIQUE problem" by Tang Pushan and Huang Zhijun (Journal of Computer Science & Technology 13(Supplement), 1998, pp 33-44). Clearly this implies P=NP. Zhu Daming, Luan Junfeng and M. A. Shaohan (all affiliated with Shandong University, China) refute these claims in their paper "Hardness and methods to solve CLIQUE" (Journal of Computer Science and Technology 16, 2001, pp 388-391).

Preserved from the frozen 2016 page. This is the historical layer, not the Register’s voice.

Adjudication status

Adjudication recorded

Recorded

This historical dossier records an adjudication in Woeginger’s note. Follow the sources in that note for its basis. The Register has not re-judged it.

As of 24 July 2026

Links printed in the dossier

Link status checked against the held 24 July 2026 probe. A dead link does not change the claim’s status.

Link printed in the historical dossier
Dead
http://portal.acm.org/citation.cfm?id=501491&dl=
DEAD:HTTPError · Link status checked 24 July 2026.
Look for an archived copy. A dead link does not change the claim’s status.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 003: An algorithm with polynomial time complexity for finding clique in a graph; HEWN: A polynomial algorithm for CLIQUE problem.” As of 24 July 2026.

BibTeX

@misc{pvnp-register-003-2026,
  author = {{The P versus NP Register}},
  title = {An algorithm with polynomial time complexity for finding clique in a graph; HEWN: A polynomial algorithm for CLIQUE problem},
  year = {2026},
  note = {Dossier 003; as of 2026-07-24}
}

Event timeline

No post-seed events are recorded for this dossier. Its imported historical record remains unchanged.