Руины Бенареса стучат в их сердца

Есть такая задача: дано несколько строк одинаковой длины из алфавита "01X". Требуется ответить на вопрос, покрывают ли они в совокупности все возможные двоичные строки той же длины, если Х может соответствовать и нулю, и единице. Вот что делают злосчастные потомки жрецов бенаресского храма:

0. Если строки нулевой длины, вернем ИСТИНА.
1. Найдем позицию, в которой во всех строках реже всего встречается Х.
2. Если в этой позиции встречаются только нули или только единицы, вернем ЛОЖЬ.
3. Поделим все строки на два подмножества: в одном будут строки, в которых в этой позиции 0 или Х, в другом 1 или Х; и вырежем эту позицию из строк - тем самым все строки стали на один символ короче.
4. Если эта же процедура, запущенная на меньшем из подмножеств, вернула ЛОЖЬ, вернем ЛОЖЬ.
5. Запустим эту же процедуру на другом подмножестве и вернем ее результат.

Задание 1. Что нужно добавить к этому алгоритму, чтобы избавить его от бенаресского проклятия?
Задание 2. Какой наглостью нужно обладать, чтобы после сообщения о неприемлемой скорости работы алгоритма заявить "It's a very involved issue"?

Ответ на задание 1:
0. Если строки нулевой длины или нашлась строка, состоящая из одних Х, вернем ИСТИНА.
Это добавление ликвидирует экспоненциальную сложность анализа таких строк.

Ответ на задание 2 оставляется в качестве упражнения.