Прочитайте превосходную (но немного трудно читаемую) статью Томаса Дж. Шеффера: Сложность удовлетворяемых задач , которая обобщает проблемы выполнимости для бесконечного класса задач, таких как 3SAT, Не все равно 3Sat и т. Д. и показывает, что каждая проблема либо в P, либо в NP-Complete.
В статье также определяются необходимые и достаточные условия для определения того, находится ли конкретная проблема в P или NP-Complete (так называемая теорема дихотомии ).
Полагаю, вы также найдете там алгоритм времени P (не очень уверенный) для проблем, которые есть в P.
Надеюсь, это поможет.