NP-полнота и сводимость

Я новичок на этом веб-сайте, поэтому прошу прощения, если этот вопрос не в том разделе. Я беру класс анализа алгоритмов и застрял на одной из моих домашних задач, и был бы признателен, если бы я мог получить некоторые рекомендации.

Проблема, на которой я застрял, заключается в том, чтобы доказать, что пустой язык и {0, 1} * - единственные языки в P, которые не являются полными для P в отношении полиномиальных сокращений (проблема 34.3-6 в третьем издании CLRS). Первая часть проблемы кажется достаточно простой (доказательство критерия пустого языка). Однако я не уверен, с чего начать, когда мне нужно подтвердить критерии для {0, 1} *. Я НЕ ищу ответа, но был бы признателен за некоторые советы о том, как я могу начать думать об этой проблеме. Заранее спасибо!


algorithm np reduction proof np-complete
person user3390653    schedule 16.03.2015    source источник
comment
Возможно, больше по теме на programmers.stackexchange.com   -  person Jonathon Reinhart    schedule 16.03.2015
comment
Я считаю, что обмен стеками по информатике больше подходит для этого типа вопросов.   -  person James    schedule 16.03.2015
comment
Возможно, тот факт, что пустой язык и {0, 1} * дополняют друг друга, должен помочь.   -  person n. 1.8e9-where's-my-share m.    schedule 16.03.2015
comment
В названии вопроса упоминается NP-полнота, а в самом вопросе - P-полнота.   -  person n. 1.8e9-where's-my-share m.    schedule 16.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Определение P Полнота в отношении полиномиального сокращения времени: проблема L является P-полной, если:

  1. L is in P
  2. Каждая задача из P сводится к L за полиномиальное время.

Для L = {}, если задана проблема X такая, что X!= {}, вам нужно найти p сокращение для каждого экземпляра X (пусть это будет x), p(x) находится в L тогда и только тогда, когда x находится в X.
Предположим, есть такой p. Однако, начиная с X != {}, есть некоторые x такие, что x находится в X, а p(x) не может быть в L, поскольку L пусто. Противоречие в существовании таких p.

Повторите то же самое для L={0,1}* на любом языке X != {0,1}*, а x не в X.

person amit    schedule 16.03.2015