Находится ли нахождение двух разных совершенных соответствий в двудольном графе co-NP?
Сначала несколько определений. Проблема co-NP является проблемой решения, где ответ "НЕТ" может быть проверен за полиномиальное время. Идеальное совпадение в двудольном графе - это набор пар узлов (пара является ребром в графе), где каждый узел встречается в этом наборе ровно один раз.
Мне дан двудольный граф nxn, и я пытаюсь выяснить, является ли проблема нахождения k различных идеальных соответствий в графе, где k= полином (n), проблемой со-NP.
Работа сделана до сих пор
Чтобы изначально упростить задачу, я считаю, что если k=2, то это проблема co-NP. Я думаю, что это правда, потому что двудольный граф не имеет 2 различных совершенных совпадений, если не существует обмена соседями между 2 узлами. Я определяю обмен соседями следующим образом. Пусть G1 будет первым множеством в графе, а G2 будет вторым множеством в графе. Обмен происходит, когда у нас есть подмножество G1, S1={A,B} и второе подмножество G2, S2={X,Y}, где {(A,X),(A,Y),(B,X),(B,Y)} принадлежит множеству ребер E. Я называю это обменом, потому что если A изначально был сопоставлен с X, а B с Y, то когда A соединяется с Y, а B с X, A и Б обменяли своих соседей. Я считаю, что единственный способ получить 2 разных идеальных соответствия - это иметь хотя бы один такой обмен.
Теперь мы можем проверить, что такой обмен не существует за полиномиальное время. Это верно, поскольку получение всех возможных подмножеств S1 и S2 имеет O(n^4) временную сложность. Это потому, что нам нужно (n выберите 2) из G1, умноженное на (n выберите 2) из G2, и это дает нам верхнюю границу n^4.
1 ответ
Я не уверен, если это проблема со-НП, но это наверняка НП. Я думаю, что вы немного перепутали определение "проверка ответа". В теории сложности подтверждение ответа означает, что вы предоставляете сертификат, подтверждающий, что ваш ответ является правильным, и такой сертификат может быть проверен (проверен) за полиномиальное время.
Например, в случае вашей проблемы, если у вас есть набор k различных идеальных совпадений, это будет хороший сертификат, проверка его означает, что он действительно является набором идеальных совпадений в вашем входном графе. Вы можете проверить это за полиномиальное время, проверив, что все ребра находятся в вашем графе, и в каждом сопоставлении нет двух ребер, имеющих общую вершину, и все они разные. Поскольку число ребер в сопоставлении является линейным, то проверка каждого сопоставления может быть выполнена за полиномиальное время, тогда, поскольку k является полиномиальным, мы проверяем это свойство для всех сопоставлений также за полиномиальное время. Наконец, проверка того, что все различны, может быть сделана за k квадратов, умноженных на полиномиальное от n, что приводит к полиномиальной сложности. Так что да, ваша проблема может быть проверена за полиномиальное время, и, следовательно, она есть в NP.
Теперь, если вы сможете найти такой сертификат за полиномиальное время, это будет достаточным доказательством того, что ваша проблема в P, а все проблемы в P - в NP и в co-NP. Таким образом, я вижу два возможных способа решения этой проблемы: вы можете доказать, что ваша проблема в P, что даст ответ "да" на ваш вопрос, или вы можете доказать, что ваша проблема является NP-полной, что докажет, что ваш ответ - нет, так как все NP-полные проблемы не в со-NP (если P = NP).
Любой другой способ доказать, что ваша проблема связана или не связана с NP, может быть очень трудным и запутанным, фактически работа, которую вы проделали до сих пор, шла к тому, чтобы доказать, что вы можете решать отрицательные случаи в полиномиальное время, которое отличается вещь, как проверка их, это докажет, что это co-NP, но потому что вы доказали, что это в P.