классы задач по сложности

[fbogomolkin]

Надо разобраться в классах задач: P, NP, NP-Complete, Co-NP, Co-NP Complete, ExpTime, Pspace, Pspace-Complete?

Если, правило понял, класс P - состоит из задач, которые могут быть решены за полиномиальное время. Класс NP - состоит из задач, для которых не известен полиномиальный алгоритм решения, но и его не существование не доказано. При этом верность любого решения может быть проверена за полиномиальное время. NP-Complete состоит из задач, к которым может быть сведена любая задача из класса NP за полиномиальное время. Класс PSpace состоит и задач, требующих полиномиальный объем памяти, но не обязательно решаемых за полиномиальное время. Все верно?

Если все верно, то вот какие вопросы (нужен краткий ответ своими словами):

1) В чем отличие классов ExpTime и NP? Насколько я понимаю и те и те решаются за полиномиальное время или не так?
2) Что такое класс PSpace-Complete ?
3) Что такое классы Co-NP и Co-NP Complete?
4) Задача дискретного логарифмирования и факторизации относятся к классы ExpTime или NP?

-- 04.07.2014, 16:06 --

Поправка к первому вопросу: решения и там и там могут быть проверены за полиномиальное время или не так?

[patzer2097]

fbogomolkin в сообщении #883882 писал(а):

В чем отличие классов ExpTime и NP? Насколько я понимаю и те и те решаются за полиномиальное время

одни "те" не решаются, а про другие "те" пока никто не знает

fbogomolkin в сообщении #883882 писал(а):

2) Что такое класс PSpace-Complete ?

а это не по адресу вопрос, попробуйте en.wikipedia.org

fbogomolkin в сообщении #883882 писал(а):

3) Что такое классы Co-NP

язык принадлежит классу co-NP, если его дополнение принадлежит NP. А про класс NP можете почитать... знаете, где?

(подсказка)

en.wikipedia.org

fbogomolkin в сообщении #883882 писал(а):

4) Задача дискретного логарифмирования и факторизации относятся к классы ExpTime или NP?

это уж смотря что Вы факторизуете, а про дискретное логарифмирование - почему бы не почитать там, где Вы узнали это название?