Replies (25)
-
@cancel, P — класс задач, решение которых находится за полиномиальное по входу время.
NP — класс задач, решение которых проверяется за полиномиальное время.
Из того, совпадают эти два класса или нет, следует очень много ништяков. -
@cancel, Над этим бьются ололо лучшие умы. Это риальни одна из важнейших задач современной математики.
-
@Avatar, Да, но разве алгоритмы уже не нужно обосновывать теоретически в плане корректности? )
