\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{510.52} %Здесь автор определяет УДК своей работы
\def\mscs{68Q17} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc О скрытых структурах булевых функций]{\large О скрытых структурах булевых функций}
\author[В.Ю. ПОПОВ]{{\bf \large \textsc{В.Ю. Попов}}\protect\orcidicon{0000-0001-9671-681X}\\ \\
%\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Vladimir Yurievich Popov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Ural Federal University,
\newline\hphantom{iii} Lenin st., 51,
\newline\hphantom{iii} 620083, Ekaterinburg, Russia}%
\email{\textcolor{blue}{popovvvv@gmail.com}}%

\thanks{\sc Popov, V.Yu.,
On the hidden structures of Boolean functions}
\thanks{\copyright \ 2023 Попов В.Ю}
%\thanks{\rm Работа поддержана РФФИ (грант 03-01-11111)}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} It is well known that Boolean functions have a number of different hidden structures.
Some structures are of significant theoretical interest.
In particular, the structures associated with the phase transition reveal important properties of the solution space of Boolean functions.
Many structures are extensively used by various heuristic algorithms to prove satisfiability of Boolean functions.
Among others, we can mention such structures as back\-doors, backbones, blocked clauses, asymmetric tautologies, hyper binary resolvents, strongly connected components, bounded vari\-ables.
Some structures are important in the context of quantum computing. In particular, we can mention the Boolean hidden shift.
Typically, to effectively use hidden structures, we need to find not only the structures themselves, but also find the proper assignments for variables.
In this paper, we consider the computati\-onal complexity of finding proper assignments for variables of hid\-den structures. In particular, we consider strongly connected com\-ponents.
It is well known that strongly connected components can be easily found in a Boolean function.
Nevertheless, we show that the problem of finding proper assignments for the variables of strongly connected components is computationally hard.\medskip

\noindent{\bf Keywords:} computational complexity, Boolean function, hidden structures, strongly connected component.
 \end{quote}
}

\bigskip

\section*{Введение}

Теория булевых функций~--- обширная область, которая давно и интенсивно развивается и имеет широкий спектр разнообразных
приложений \cite{Crama__Hammer__2011}. Исследования булевых функций позволили выявить большое количество различных скрытых структур
\cite{Hemaspaandra__Narvaez__2021},
идентификация которых существенно облегчает дальнейший анализ булевых функций и установление их свойств.

Некоторые структуры представляют существенный теоретический интерес.
В частности, структуры, которые ассоциированы с фазовым переходом вскрывают важные свойства пространства
решений булевых функций (см., например,
\cite{Cheeseman__Kanefsky__1991,Mitchell__Selman__1992,Sleegers__Olij__2000}.
Фазовый переход характерен для многих физических систем
\cite{Hartmann__Weigt__2005,Mezard__Montanari__2009,Moore__Mertens__2011}.
Недавно доказанная пороговая гипотеза описывает значительное изменение поведения функций
в области фазового перехода
\cite{Ding__Sly__2016,Ding__Sly__2022,Park__Pham__2024,Park__Vondrak__2024}.
В работах было установлено, что для проблемы выполнимости и проблемы коммивояжера
имеется тесная связь между фазовым переходом и явлением замораживания переменных
\cite{Kirkpatrick__Toulouse__1985,Monasson__Zecchina__1996,Monasson__Zecchina__1997,Monasson__Zecchina__Kirkpatrick__1999_2},
которое позднее было формализовано как одна из скрытых структур: хребты
\cite{Schneider__Froschhammer__Morgenstern__1996,Monasson__Zecchina__Kirkpatrick__1999,Bollobas__Borgs__Chayes__2001}.
Хребты объясняют принципиально важную аномалию в поведении булевых функций в области фазового перехода:
хотя средное вычислительные затраты на поиск решения
для проблемы выполнимости ростут линейно с увеличением количества переменных,
для небольшой доли булевых функций наблюдается экспоненциальный рост затрат
\cite{Selman__Kirkpatrick__1996}, что обусловлено присутствием хребтов в соответствующих булевых функциях
\cite{Monasson__Zecchina__Kirkpatrick__1999}.

Некоторые структуры важны в контексте квантовых вычислений. В частности, мы можем
упомянуть булев скрытый сдвиг \cite{Childs__Kothari__Ozols__Roetteler__2013}.
Использование скрытой подгруппы \cite{Childs__vanDam__2010}
лежит в основе эффективности ряда квантовых алгоритмов
\cite{Boneh__Lipton__1995,Regev__2004,Kuperberg__2005,Hallgren__2007}.
Проблема булева скрытого сдвига является естественным аналогом проблемы
скрытой подгруппы для булевых функций \cite{Childs__Kothari__Ozols__Roetteler__2013}.

Многие скрытые структуры широко используются различными эвристическими алгоритмами для доказательства
выполнимости булевых функций.
Среди прочих мы можем упомянуть такие структуры, как бэкдоры
\cite{Gaspers__Misra__Ordyniak__Szeider__Zivny__2017,Samer__Szeider__2008,Szeider__2010},
хребты \cite{AlYahya__Menai__Mathkour__2022,Menai__Batouche__2006,Biere__Faller__Fazekas__2024},
блокированные дизъюнкции \cite{Biere__Jarvisalo__Kiesl__2021},
асимметричные тавтологии \cite{Biere__Jarvisalo__Kiesl__2021,Kirchweger__Szeider__2024},
гипербинарные резольвенты \cite{Biere__Jarvisalo__Kiesl__2021,Heule__Jarvisalo__Biere__2013},
сильно связанные компоненты \cite{Heule__Jarvisalo__Biere__2010,Li__2000,Vukmirovic__Blanchette__Heule__2023},
ограниченные переменные \cite{Biere__Jarvisalo__Kiesl__2021}.

Для различных скрытых структур вычислительная сложность выявления их присутствия и нахождения в явном виде
существенно отличается. Некоторые скрытые структуры сравнительно легко обнаружить и найти в явном виде.
Для некоторых структур вопрос о присутствии этих структур в булевой функции является вычислительно трудным.
К числу вычислительно трудных скрытых структур относятся бэкдоры и хребты.
Вопрос о существовании бэкдоров исследовался с точки зрения параметрической сложности
\cite{Nishimura__Ragde__Szeider__2005}.
Хотя проблема существования сильных бэкдоров для хорновских бэкдоров и бэкдоров в 2-конъюнктивной нормальной форме
разрешима с фиксированным параметром, проблема существования слабых бэкдоров является $W[2]$-трудной
для этих бэкдоров
\cite{Nishimura__Ragde__Szeider__2005}.
Без фиксации параметра обе проблемы являются {\bf NP}-полными
\cite{Nishimura__Ragde__Szeider__2005}. Для более широкого класса бэкдоров в работе
\cite{Dilkina__Gomes__Sabharwal__2014}
показано, что проблема существования бэкдоров является одновременно {\bf NP}-трудной и {\bf co-NP}-трудной.
В предположении ${\bf P} \not= {\bf NP}$ в работе \cite{Kilby__Slaney__Thiebaux__Walsh__2005}
показано, что не существует аппроксимационной процедуры, которая бы гарантировала
нахождение достаточно большого хребта за полиномиальное время.
Зафиксируем некоторое множество булевых функций ${\mathcal F}$ и
действительное число $\beta$, $0 < \beta < 1$. Обозначим через
$L({\mathcal F}, \beta)$ язык, состаящий из всех булевых функций $f$, $f \in {\mathcal F}$, таких, что
существует хребет $S$, $S \subseteq V(f)$, удовлетворяющий неравенству $\vert S \vert \geq \beta \vert V(f) \vert$.
Для любого действительного числа $\beta$, $0 < \beta < 1$,
существует генерируемое за полиномиальное время множество булевых функций ${\mathcal F}$
такое, что язык $L({\mathcal F}, \beta)$ является {\bf NP}-полным \cite{Hemaspaandra__Narvaez__2021}.

Обычно для эффективного использования скрытых структур мы нуждаемся в нахождении не только самих
структур, но и нахождении правильных значений переменных.
Более того, во многих случаях мы точно знаем, что булева функция является выполнимой. В частности, это типично для задач,
связанных с защитой информации. Например, при атаке на основе проблемы выполнимости на защищенную аппаратную часть
мы знаем, что ключ существует, нам необходимо его найти (см., например, \cite{Fowler__Mohammed__Shihab__Broadfoot__2025}).
Восстановление исходных данных для хеш-функции
естественным образом предполагает их существование (см., например, \cite{Lafitte__Nakahara__VanHeule__2014}).
Информация об анализируемой булевой функции
может включать не только факт ее выполнимости. Например, при решении задач, связанных с защитой от криптоанализа,
можно исходить из наличия некоторых вполне определенных скрытых структур
(см., например, \cite{Shi__Liu__Li__2023}).
В некоторых случаях мы можем быть проинформированы даже о способе сокрытия специфических структур
(см., например, \cite{Matsui__Cai__2021}).
В этих случаях для заведомо выполнимой функции с известными структурами нам необходимо найти конкретные значения
переменных этих структур.

Следует отметить, что трудность нахождения значений переменных не всегда напрямую коррелирует с трудностью
обнаружения скрытых структур. В частности, в случае хребтов трудной является как задача обнаружения хребтов
\cite{Kilby__Slaney__Thiebaux__Walsh__2005,Hemaspaandra__Narvaez__2021},
так и задача нахождения значений для их переменных.
С другой стороны,
хотя проблема существования сильных бэкдоров для хорновских бэкдоров и бэкдоров в 2-конъюнктивной нормальной форме
является {\bf NP}-полной,
присутствие сильных бэкдоров обеспечивает проблеме выполнимости для соответствующих функций разрешимость с фиксированным
параметром \cite{Nishimura__Ragde__Szeider__2005}.

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

\section{Основные определения}

Для произвольной булевой функции $f(x_1,x_2, \dots , x_n)$, зависящей от переменных $x_1,x_2, \dots , x_n$,
будем говорить, что функция $f$ представлена в 
$k$-конъ\-юнкт\-ив\-ной нормальной форме,
если функция $f$ имеет вид
\begin{equation}\label{f0}
\wedge_{i=1}^m C_i,
\end{equation}
где для любого $i$, $1 \leq i \leq m$, функция $C_i$ является дизъюнкцией не более $k$ литералов,
т.е.
\begin{equation}\label{f1}
C_i=\vee_{j=1}^{p_i} u_{i,j},
\end{equation}
$$u_{i,j} \in \{ x_1, x_2, \dots , x_n, \neg x_1, \neg x_2, \dots , \neg x_n \},$$
$p_i \leq k$.
Для произвольного литерала $u$ будем предполагать, что $u$ графически равен $\neg \neg u$.
Если конкретное значение $k$ не является существенным, то вместо $k$-конъ\-юнкт\-ив\-ной нормальной формы
мы будем говорить просто о конъюнктивной нормальной форме.

Графом импликаций \cite{Aspvall__Plass__Tarjan__1979}
булевой функции $f(x_1,x_2, \dots , x_n)$ в конъюнктивной нормальной форме
будем называть ориентированный граф
$G_f$ с множеством вершин
$$V_f = \{ x_1, x_2, \dots , x_n, \neg x_1, \neg x_2, \dots , \neg x_n \}$$
и множеством ребер $E_f$.
Предполагается, что множество $E_f$ содержит ребра $(\neg u_{i,1}, u_{i,2})$ и $(\neg u_{i,2}, u_{i,1})$
тогда и только тогда, когда $C_i= u_{i,1} \vee u_{i,2}$ и литералы $u_{i,1}$ и $u_{i,2}$ соответствуют
различным переменным. Кроме пар ребер $(\neg u_{i,1}, u_{i,2})$ и $(\neg u_{i,2}, u_{i,1})$,
множество $E_f$ ребер не содержит. В частности, дизъюнкции, содержащие больше двух литералов или только один литерал,
в формировании множества ребер не участвуют.

Ориентированный граф называется сильно связным, если для любых двух вершин $u$ и $v$ существуют путь по ребрам из вершины $u$ в вершину $v$ и путь из вершины $v$ в вершину $u$ \cite{Tarjan__1972}.
Пусть $G=(V,E)$~--- ориентированный граф с множеством вершин $V$ и множеством ребер $E$.
Мы можем определить отношение эквивалентности на множестве вершин, полагая, что вершины $u$ и $v$ из множества $V$
эквивалентны, если существуют путь по ребрам из вершины $u$ в вершину $v$ и путь из вершины $v$ в вершину $u$.
Это отношение задает множество
$$\{ V_i \mid 1 \leq i \leq n\}$$
попарно различных классов эквивалентности.
Рассмотрим множество
$$\{ G_i=(V_i,E_i) \mid 1 \leq i \leq n, E_i=\{(u,v) \in E \mid u \in V_i, v \in V_i \}\}$$
подграфов графа $G$. Каждый граф $G_i$ является сильно связным и не является собственным подграфом
никакого сильно связного подграфа графа $G$. Следуя \cite{Tarjan__1972}, графы $G_i$ будем называть сильно связными компонентами графа $G$.

\section{Вычислительная сложность нахождения  значений переменных}

Нахождение сильно связных компонент представляется весьма полезным при анализе булевых функций.
По построению сильно связные компоненты определяют множества литералов, принимающих одно и то же значение.
Поэтому, заменяя множество переменных на одну переменную, можно существенно снизить размерность пространства
перебора. Кроме того, нахождение сильно связных компонент существенно повышает эффективность ряда других
методов анализа булевых функций. В частности, это относится к методу зондирования при помощи неудачного литерала
(см. \cite{Biere__Jarvisalo__Kiesl__2021,LeBerre__2001,Lynce__MarquesSilva__2003}).
Для нахождения сильно связных компонент произвольного ориентированного графа $G$ хорошо известен ряд эффективных алгоритмов
\cite{Tarjan__1972,Sharir__1981,Fleischer__Hendrickson__Pinar__2000}. Учитывая легкость обнаружения,
сильно связные компоненты широко используются при анализе булевых функций
(см., например,
\cite{Brafman__2004,Reeves__Heule__Bryant__2024,VanGelder__2005}).
Однако следует отметить, что
для различных скрытых структур их обнаружение имеет существенно различные последствия для дальнейшего
анализа булевых функций. Например, обнаружение некоторых бэкдоров дает сравнительно эффективный алгоритм
для полного решения проблемы выполнимости для соответствующих функций
\cite{Nishimura__Ragde__Szeider__2005}.
Преобразование булевых функций к конъюнктивной нормальной форме, содержащей дизъюнкции из одного литерала,
автоматически устанавливает значения соответствующих литералов.
С этой точки зрения сильно связные компоненты не столь эффективны: их обнаружение не ведет к непосредственному
нахождению значений каких-либо переменных.

В общем случае поиск значений переменных сильно связных компонент может развиваться в двух направлениях:
доказательство того, что переменные могут принимать единственное значение;
доказательство того, что для переменных сильно связной компоненты возможно свободное назначение,
т.е. выполнимость булевой функции не зависит от выбора общего значения эквивалентных переменных сильно
связной компоненты.
В первом случае переменные сильно связной компоненты являются по определению частью хребта.
Соответственно, задача нахождения их значений является вычислительно трудной \cite{Hemaspaandra__Narvaez__2021_2}.
Решение вопроса о свободном назначении тоже является {\bf NP}-трудной задачей.

\begin{proposition}
\label{TT_01}
Задача выяснения возможности свободного назначения для эквивалентных переменных сильно
связной компоненты является {\bf NP}-трудной.
\end{proposition}

\begin{proof}
Для доказательства предложения достаточно рассмотреть булеву функцию
\begin{equation}\label{f2}
h(x) \wedge (x \vee f),
\end{equation}
где $h(x)$~--- сильно связная компонента, содержащая переменную $x$,
а $f$~--- произвольная функция, не имеющая общих переменных с $h(x)$.
Если функция $f$ выполнимой не является, то выполнимость функции (\ref{f2}) требует, чтобы выполнялось равенство
$x=1$. Соответственно, в этом случае свободное назначение для эквивалентных переменных сильно
связной компоненты $h(x)$ невозможно.
Если функция $f$ является выполнимой, то мы можем считать выбор значения переменной $x$ свободным:
это ограничивает выбор значений для переменных функции $f$, но не выводит нас за рамки решения проблемы выполнимости
для функции (\ref{f2}).
Таким образом, возможность свободного назначения для переменной $x$ равносильна выполнимости булевой функции $f$.
\end{proof}

Заметим, что утверждение предложения \ref{TT_01}, как и результат \cite{Hemaspaandra__Narvaez__2021_2}, не являются
существенным препятствием для поиска значений переменных сильно связных компонент, поскольку
эти результаты не выводят нас за рамки трудности исходной задачи: мы просто одну трудную задачу сводим к другой,
имеющей аналогичную трудность. Однако в контексте использования конкретного решателя
решение вопроса о свободном назначении может быть значительно труднее,
чем вопроса выполнимости исходной функции.
Например, хорошо известно, что близкие по виду функции
$(\neg x \vee y) \wedge (x \vee \neg y)$ и
$(x \vee y) \wedge (x \vee \neg y)$ имеют существенно различные свойства
(см., например, \cite{Li__2003}).

Предполагая свободу выбора некоторых переменных,
мы, вообще говоря, ограничиваем свободу выбора других переменных, что может иметь существенно различные последствия.
Например, если в функции $x \vee f$, где $x$~--- переменная, а $f$~---
нетривиальная функция, для переменной $x$ допустить свободный выбор,
то возможность свободного выбора переменных функции $f$ будет ограничена.
Однако это ограничение~--- лишь сведение исходной задачи к подзадаче.
Если же допустить свободный выбор для переменной $x$ в функции $f \rightarrow x$, где $x$~--- переменная, а $f$~---
нетривиальная функция, то нам потребуется рассматривать выполнимость функции $\neg f$.
Структура функции $\neg f$ может существенно отличаться от структуры функции $f$,
что для конкретного решателя может сделать допущение свободного выбора для переменной $x$
неприемлемым. Поэтому в некоторых случаях элиминация импликации~--- допущение свободного выбора для переменной,
стоящей в заключении импликации~--- считается недопустимой.

\begin{proposition}
\label{TT_02}
При запрете на элиминацию импликации задача выяснения возможности свободного назначения для эквивалентных переменных сильно
связной компоненты является {\bf DP}-трудной.
\end{proposition}

\begin{proof}
Доказательство предложения будет основано на сведении от следующей хорошо известной {\bf DP}-полной проблемы
(см., например, \cite{Papadimitriou__1994}, теорема 17.1).

{\sc SAT-UNSAT.}

{\sc Дано:} {\it Булевы функции $f$ и $g$, каждая из которых представлена в конъюнктивной нормальной форме,
причем каждая дизъюнкция содержит по три литерала.}

{\sc Вопрос:} {\it Верно ли, что функция $f$ выполнима, а функция $g$ выполнимой не является?}

Рассмотрим произвольные булевых функции $f$ и $g$ такие, что $f$ и $g$ не имеют общих переменных,
каждая из функций $f$ и $g$ представлена в конъюнктивной нормальной форме.
Для булевых функции $f$ и $g$ рассмотрим булеву функцию
\begin{equation}\label{f3}
s(f,g)=h(x,y) \wedge (x \vee f) \wedge (g \rightarrow y)
\end{equation}
такую, что $h(x,y)$~--- сильно связная компонента, содержащая эквивалентные переменные $x$ и $y$,
функции $f$, $g$ и $h$ попарно не имеют общих переменных.
Для выполнимости функции (\ref{f3}) сильно связная компонента $h(x,y)$ требует лишь выбора одинаковых значений
для эквивалентных переменных $x$ и $y$.
Если функция $f$ выполнимой не является, то выполнимость функции (\ref{f3}) требует, чтобы выполнялось равенство
$x=1$. Соответственно, в этом случае свободное назначение для эквивалентных переменных сильно
связной компоненты $h(x,y)$ невозможно.
Если функция $f$ является выполнимой, то мы можем считать выбор значения переменной $x$ свободным:
это ограничивает выбор значений для переменных функции $f$, но не выводит нас за рамки решения проблемы выполнимости
для функции (\ref{f2}).
Аналогично, если функция $g$ является выполнимой, то выбор значения переменной $y$ ограничен значением $g$:
поиск опровергающего набора значений для функции $g$ может вести к существенному усложнению поиска.
Если функция $g$ не является выполнимой, то выбор значения переменной $y$ можно считать свободным.
Учитывая то, что в проблеме {\sc SAT-UNSAT} множества переменных функций $f$ и $g$ можно считать не пересекающимися,
при запрете на элиминацию импликации задача выяснения возможности свободного назначения для эквивалентных переменных сильно
связной компоненты требует решения проблемы {\sc SAT-UNSAT}, т.е. является {\bf DP}-трудной.
\end{proof}

Хотя в общем случае поиск значений для переменных сильно связных компонент является вычислительно трудной задачей,
во многих случаях мы можем располагать информацией о значениях некоторых переменных. Например, значения могут быть выявлены в результате
анализа другими методами, знание значений может быть предположением при поиске грубой силой.
Однако знание значений некоторых переменных не означает, что их подстановка в булеву функцию является оптимальным
действием для дальнейшего анализа: в результате подстановки, вообще говоря, может получиться более трудная для анализа функция.
При анализе булевых функций некоторые преобразования направлены на формирование скрытых структур заданного типа
в явном виде, а некоторые используются для удаления соответствующих структур.
Это обусловлено тем, что присутствие многих скрытых структур может быть как полезным, так и вредным.
Ярким примером такой скрытой структуры являются блокированные дизъюнкции.
В некоторых случаях элиминация блокированных дизъюнкций ведет к существенному повышению производительности решателя
\cite{Biere__Lonsing__Seidl__2011,Heule__Kullmann__Marek__2016,Jarvisalo__Biere__Heule__2010}.
В других случаях добавление блокированных дизъюнкций повышает производительность решателя
\cite{Fleury__Kaufmann__2024,Subercaseaux__Heule__2023}. Более того,
добавление блокированных дизъюнкций может приводить к экспоненциальному уменьшению кратчайшего опровержения формулы
\cite{Kiesl__RebolaPardo__Heule__2018,Kullmann__1999}.
Таким образом, для некоторой функции $f$ наличие блокированных дизъюнкций может быть полезно,
а для некоторой функции $g$ присутствие блокированных дизъюнкций может быть нежелательным.
Соответственно, преобразование, например, булевой функции $f \wedge g$ потребует подхода, основанного
на встречном использовании добавления и элиминации. Заметим, что выработка оптимальной стратегии
для блокированных дизъюнкций является {\bf NP}-трудной \cite{Subercaseaux__2024}.
Сильно связные компоненты относятся к числу таких структур. С одной стороны, элиминация сильно связных компонент
позволяет значительно сократить пространство решений и упрощает перебор.
С другой стороны, введение эквивалентных переменных и, соответственно, добавление сильно связных компонент
часто используется для упрощения общей структуры булевой функции. В частности, это преобразование используется
для получения планарных формул.

В общем случае булева функция $f$ может иметь некоторое подмножество переменных
$X=\cup_{i \in I} X_i$, являющееся объединением множеств переменных $X_i$ сильно связных компонент
$G_i$, $i \in I$, графа $G_f$, для которых возможна элиминация посредством нахождения значений переменных, и некоторое
подмножество переменных $Y$, для которых появление связных компонент не является желательным.
Обычно у нас появляется возможность выделять множества $X$ и $Y$ и рассуждать об их свойствах в том случае,
когда анализируемая булева функция $f$ является частью более общей функции $g$, некоторые свойства
которой нам известны.
Говоря о том, что для некоторых переменных возможна элиминация посредством нахождения значений переменных,
мы подразумеваем, что у нас есть некоторая эффективная процедура, которая за полиномиальное время позволяет находить значения этих
переменных в явном виде.
Подставляя значение некоторой переменной, мы подставляем значения и эквивалентных переменнных.
Поэтому мы полностью элиминируем некоторую сильно связную компоненту,
поскольку компоненты состоят только из эквивалентных переменных.
Однако при этом преобразуется вся булева функция $f$. В результате такого преобразования
могут появиться новые сильно связные компоненты или новые переменные в уже существующих компонентах.
В некоторых случаях это ведет к существенному упрощению или даже полному решению задачи выполнимости,
в некоторых к нежелательным последствиям.
Исходя из этого, представляет интерес следующая проблема максимальной подстановки значений переменных
сильно связных компонент.

{\sc MS.}

{\sc Дано:} {\it Булева функция $f$ с множеством переменных $V$. Множество $X=\cup_{i \in I} X_i \subseteq V$ переменных сильно связных
компонент $G_i$, $i \in I$, графа $G_f$, для которых может быть найдено значение. Множество переменных $Y \subseteq V$.
Натуральное число $n$.}

{\sc Вопрос:} {\it Существует ли множество $Z=\cup_{j \in J \subseteq I} X_j \subseteq X$ такое, что $\vert Z \vert \geq n$, при подстановке значений переменных
из множества $Z$ ни одна переменная множества $Y$ не попадает в сильно связные компоненты графа $G_f$?}

\begin{proposition}
\label{TT_03}
Проблема {\sc MS} является {\bf NP}-полной.
\end{proposition}

\begin{proof}
Предположим, что у нас есть некоторое множество $Z$, являющееся потенциальным решением проблемы {\sc MS}
для булевой функции $f$. Тогда мы можем за полиномиальное время найти значения всех переменных из множества $Z$,
подставить найденные значения в функцию $f$ и осуществить упрощение: если литерал принимает значение $0$, то литерал удаляется
из дизъюнкции; при единичном значении литерала удаляется вся дизъюнкция. После этого мы можем, например, используя
алгоритм \cite{Tarjan__1972}, вычислить сильно связные компоненты полученной булевой функции и выяснить,
принадлежат ли переменные множества $Y$ какой-либо сильно связной компоненте. Таким образом, проблема {\sc MS}
принадлежит классу {\bf NP}.

Для доказательства трудности проблемы {\sc MS} мы рассмотрим проблему точного покрытия 3-множествами,
которую можно сформулировать следующим образом.

{\sc X3C.}

{\sc Дано:} {\it Натуральное число $q$. Множество $U$ такое, что $\vert U \vert = 3q$.
Семейство $M$ подмножеств множества $U$ такое, что для любого $S \in M$ выполняется равенство $\vert S \vert = 3$.}

{\sc Вопрос:} {\it Верно ли, что семейство $M$ содержит точное покрытие множества $U$,
т.е. такое семейство $M^{\prime} \subseteq M$, что $U=\cup_{S \in M^{\prime}} S$ и $\vert M^{\prime} \vert = q$?}

Хорошо известно, что проблема {\sc X3C} является {\bf NP}-полной (см., например, \cite{Papadimitriou__1994},
следствие из теоремы 9.9). Для произвольных исходных данных $(q, U, M)$ проблемы {\sc X3C} определим некоторую булеву функцию
$f(q, U, M)$.
Пусть для некоторого натурального числа $p$ выполняется равенство
\begin{equation}\label{f4}
M=\{ M_1, M_2, \dots , M_p\}.
\end{equation}
Без ограничения общности мы можем предполагать, что $p>1$, $q>1$.
Над множеством переменных $X \cup Y$, где
\begin{eqnarray}
&Y= \{ y[1], y[2] \} \label{f5_0}\\
&X= \{ x[M_s,i] \mid 1 \leq s \leq p, 1 \leq i \leq p^3 \} \cup \nonumber\\
&\{ x[M_s,M_t] \mid 1 \leq s \leq p, 1 \leq t \leq p, s \not= t \}, \label{f5}
\end{eqnarray}
рассмотрим следующие булевы функции:
\begin{eqnarray}
&g_s= (\neg x[M_s,p^3] \vee x[M_s,1]) \wedge \nonumber\\
&( \wedge_{1 \leq i < p^3}
(\neg x[M_s,i] \vee x[M_s,i+1]) ) \wedge \nonumber\\
&( \wedge_{s \not= t, M_s \cap M_t \not= \emptyset, 1 \leq t \leq p}
(\neg x[M_s,1] \vee x[M_s,M_t]) \wedge  \nonumber\\
&(\neg x[M_s,M_t] \vee x[M_s,1]) ), \label{f6}\\
&h_{s,t}=(\neg y[1] \vee y[2] \vee x[M_s,M_t] \vee x[M_t,M_s]) \wedge  \nonumber\\
&(\neg y[2] \vee y[1] \vee x[M_s,M_t] \vee x[M_t,M_s]), \label{f7}\\
&f(q, U, M)= ( \wedge_{1 \leq s \leq p} g_s ) \wedge ( \wedge_{s \not= t, 1 \leq s \leq p, 1 \leq t \leq p} h_{s,t} ).
\label{f8}
\end{eqnarray}
Согласно определениям (\ref{f5_0}) и (\ref{f5}), множества $X$ и $Y$
не пересекаются.
Непосредственной проверкой можно убедиться, что множество переменных $V$ булевой функции $f(q, U, M)$
равно $X \cup Y$. Используя равенства (\ref{f6})~-- (\ref{f8}),
легко понять, что функции $g_s$ задают сильно связные компоненты. Соответственно,
\begin{eqnarray}
&X= \cup_{1 \leq s \leq p} X_s, \label{f9}\\
&X_s= \{ x[M_s,i] \mid 1 \leq i \leq p^3 \} \cup \nonumber\\
&\{ x[M_s,M_t] \mid  1 \leq t \leq p, s \not= t, M_s \cap M_t \not= \emptyset \}. \label{f10}
\end{eqnarray}
Будем предполагать, что переменные множества $X$ могут принимать только значение $0$. Пусть $n=p^3q$.

Предположим, что существует множество $Z$ такое, что $\vert Z \vert \geq n$, при подстановке значений переменных из множества $Z$ ни одна переменная множества $Y$ не попадает в сильно связные компоненты.
Из соотношения (\ref{f9}) следует, что
\begin{eqnarray}
&Z= X_{j_1} \cup \dots \cup  X_{j_k},\label{f11}
\end{eqnarray}
где $k \leq p$.
Непосредственно из соотношения (\ref{f10}) следует, что для любого $r$, $1 \leq r \leq k$ выполняется неравенство
$\vert X_{j_r} \vert \leq P^3+p$.
В силу соотношения (\ref{f11}) отсюда вытекает неравенство $\vert Z \vert \leq k(P^3+p)$.
Поэтому в силу соотношений $n=p^3q$, $\vert Z \vert \geq n$
выполняется неравенство $p^3q \leq k(P^3+p)$. Следовательно, $k \geq q$.
Так как при подстановке значений переменных из множества $Z$ ни одна переменная множества $Y$ не попадает в сильно связные компоненты,
для любых $s$ и $t$
таких, что
$s \not= t$, $M_s \cap M_t \not= \emptyset$, $1 \leq s \leq p$, $1 \leq t \leq p$,
либо $X_s \not\subseteq Z$, либо $X_t \not\subseteq Z$.
Следовательно, семейство $M$ содержит точное покрытие множества $U$.
В частности,
мы можем взять в качестве $M^{\prime}$ множество
$$M_{j_1} \cup \dots \cup  M_{j_k}.$$

Предположим теперь, что
семейство $M$ содержит точное покрытие множества $U$.
В силу соотношения (\ref{f4}) мы можем полагать, что
$$M^{\prime}=M_{j_1} \cup \dots \cup  M_{j_q}.$$
Тогда в качестве $Z$ мы можем взять множество
$$X_{j_1} \cup \dots \cup  X_{j_q}.$$

Таким образом, семейство $M$ содержит точное покрытие множества $U$ тогда и только тогда, когда
для функции $f(q, U, M)$
существует ли множество $Z= \subseteq X$ такое, что $\vert Z \vert \geq n$ и при подстановке значений переменных
из множества $Z$ ни одна переменная множества $Y$ не попадает в сильно связные компоненты.
Отсюда в силу {\bf NP}-полноты проблемы {\sc X3C} вытекает {\bf NP}-трудность проблемы {\sc MS}.
\end{proof}

\section{Машины Тьюринга для класса {\bf TFNP}}

Результаты предложений \ref{TT_01} и \ref{TT_02} показывают, что нахождение значений для переменных сильно связных компонеет
может быть не менее трудным, чем решение проблемы выполнимости. Более того, некоторое усложнение условия анализа
булевой функции может сделать задачу нахождения значений переменных существенно более трудной, чем прямое
решение проблемы выполнимости.
Это согласуется с ранее известными результатами, полученными для других скрытых структур
\cite{Nishimura__Ragde__Szeider__2005,Dilkina__Gomes__Sabharwal__2014,Kilby__Slaney__Thiebaux__Walsh__2005,Hemaspaandra__Narvaez__2021,Hemaspaandra__Narvaez__2021_2}.
Однако все эти результаты, за исключением
\cite{Hemaspaandra__Narvaez__2021_2}, относятся к случаю, когда анализируемая функция теоретически может и не выполняться,
т.е. не имеют силы для класса {\bf TFNP}, состоящего из проблем, которые всегда имеют решение.
Традиционно задачи криптографии и большинства других приложений, связанных с защитой информации,
предполагают, что решение имеется всегда, т.е. относятся к классу {\bf TFNP}.
Соответственно, для таких задач на сегодняшний день известен лишь результат \cite{Hemaspaandra__Narvaez__2021_2}.
Хотя результат \cite{Hemaspaandra__Narvaez__2021_2} получен только для хребтов, он может быть распространен
и на сильно связные компоненты, и на ряд других скрытых структур.
Однако результат \cite{Hemaspaandra__Narvaez__2021_2} справедлив лишь в предположении
${\bf P} \not= {\bf NP} \cap \hbox{\bf co-NP}$, т.е. даже доказательство неравенства
${\bf P} \not= {\bf NP}$ не гарантирует трудности нахождения значений переменных в классе {\bf TFNP}.
Отсутствие более сильного обоснования для криптографических задач обусловлено тем, что
большинство методов доказательства трудности опирается на наличие полных проблем, а для класса {\bf TFNP}
полные проблемы неизвестны. Более того, основной гипотезой на сегодняшний день является предположение о том,
что класс {\bf TFNP} полных проблем не имеет
\cite{Megiddo__Papadimitriou__1991,Goldberg__Papadimitriou__2018,Goos__Hollender__Jain__Maystre__Pires__Robere__Tao__2024}.

Вопрос о существовании в некотором классе полных проблем тесно связан с существованием
для этого класса рекурсивно перечислимого множества машин.
Для доказательства полноты некоторого языка $L$ необходимо показать, что любой язык из класса
сводится к $L$. Соответственно, любое конструктивное доказательство
полноты должно опираться на некоторый способ перечисления языков класса.
Рекурсивные свойства классов вычислительной сложности рассматривались в работах
\cite{Hartmanis__Stearns__1965,Young__1969,Lewis__1970,Borodin__1972}.
В частности, в работе
\cite{Hartmanis__Stearns__1965} (теорема 5)
было показано, что для произвольной функции времени $T$ не существует алгоритма,
определяющего по произвольной последовательности $\alpha$, вычислима ли последовательность $\alpha$
за время $T$.
Согласно \cite{Lewis__1970}, для произвольной рекурсивной функции $T$ существует мера вычислительной сложности,
относительно которой класс вычислительной сложности, задаваемый функцией $T$, не является рекурсивно перечислимым.
В работе
\cite{Landweber__Robertson__1972}
было введено понятие рекурсивной представимости класса вычислительной сложности:
класс вычислительной сложности $R$, состоящий их функций, называется рекурсивно представимым, если существует рекурсивное
множество индексов $I$ такое, что для любой функции из $R$ множество $I$ содержит по крайней мере один индекс,
множество $I$ не содержит индексов функций, которые не принадлежат $R$.
Как показано в работе
\cite{Landweber__Robertson__1972},
не существует алгоритма, определяющего по произвольному классу вычислительной сложности, является ли он рекурсивно представимым.
На необходимость эффективного множества машин для исследования структурных вопросов для классов вычислительной сложности
{\bf P} и {\bf NP}
было обращено внимание в работах
\cite{Baker__Gill__Solovay__1975,Ladner__1975}: в работе
\cite{Baker__Gill__Solovay__1975}
была предложена модель машины с часами, а в работе
\cite{Ladner__1975}
использовались машины со счетчиком.
В работе
\cite{Landweber__Lipton__Robertson__1981} (см. также \cite{Chew__Machtey__1981})
было показано, что если ${\bf P} \not= {\bf NP}$, то класс ${\bf NP} \backslash {\bf P}$ не является рекурсивно представимым.
Следует отметить, что список классов вычислительной сложности, для которых доказана рекурсивная представимость,
сравнительно невелик \cite{Schoning__1982}.
Для произвольной машины Тьюринга $M$ обозначим через $L(M)$ язык, распознаваемый машиной $M$.
Как показано в работе \cite{Kowalczyk__1984},
в классе ${\bf NP} \cap \hbox{\bf co-NP}$ существуют полные языки тогда и только тогда, когда существует рекурсивное
множество пар недетерминированных полиномиальных машин Тьюринга $\{ (M_i,N_i) \mid i \in {\Bbb N}\}$ такое,
что $L(M_i)=\overline{L(N_i)}$, ${\bf NP} \cap \hbox{\bf co-NP} = \{ L(M_i) \mid i \in {\Bbb N}\}$.
В работе
\cite{Hartmanis__Hemachandra__1988}
показано, что для класса {\bf UP} существует полный язык тогда и только тогда, когда существует рекурсивно
перечислимое множество однозначных недетерминированных машин $\{ N_i \mid i \in {\Bbb N}\}$ такое,
что ${\bf UP} = \{ L(N_i) \mid i \in {\Bbb N}\}$.
В связи с этими результатами представляет интерес следующее утверждение.

\begin{proposition}
\label{TT_04}
Множество всех полиномиальных недетерминированных машин Тьюринга, решающих проблемы из класса {\bf TFNP},
не является рекурсивно перечислимым.
\end{proposition}

\begin{proof}
Как обычно, мы полагаем, что произвольная $k$-ленточная машина Тьюринга
${\frak M}$ для некоторых натуральных чисел $n$ и $m$
задается множеством внутренних состояний считывающего устройства
\begin{equation}\label{e1}
Q=\{ q_0, q_1, q_2, \dots , q_n \},
\end{equation}
где $q_0$~--- выделенное начальное состояние,
$q_1$~--- допускающее заключительное состояние,
$q_2$~--- отвергающее заключительное состояние,
алфавитом ленты
\begin{equation}\label{e2}
\Delta = \{ a_0 , a_{1}, \dots, a_{m}\},
\end{equation}
где $a_0$~--- выделенный пустой символ,
и отображением перехода
\begin{equation}\label{e3}
\delta : (Q \backslash \{ q_1, q_2 \} ) \times \Delta^k \rightarrow Q \times \Delta^k \times \{ -1, 0, 1 \}^k .
\end{equation}
Произвольная команда
\begin{equation}\label{e4}
q_{i_1}a_{j_{1,1}}a_{j_{2,1}}\dots a_{j_{k,1}} \rightarrow q_{i_2}a_{j_{1,2}}a_{j_{2,2}}\dots a_{j_{k,2}}d_1d_2\dots d_k,
\end{equation}
где $q_{i_1} \in Q \backslash \{ q_1, q_2 \}$, $q_{i_2} \in Q$, $0 \leq j_{p,s} \leq m$, $d_p \in \{-1, 0, 1\}$, $1 \leq p \leq k$, $1 \leq s \leq 2$,
определяется соотношением
$$\delta (q_{i_1},a_{j_{1,1}},a_{j_{2,1}},\dots ,a_{j_{k,1}}) =
(q_{i_2},a_{j_{1,2}},a_{j_{2,2}},\dots ,a_{j_{k,2}},d_1,d_2,\dots ,d_k)$$
по отображению перехода (\ref{e3}). Программа
машины ${\frak M}$ состоит из множества всех команд вида (\ref{e4}).
Исходя из введенных определений, произвольная машина Тьюринга ${\frak M}$ может быть задана упорядоченной тройкой
$(Q,\Delta,\delta)$, где $Q$, $\Delta$ и $\delta$ определяются соотношениями (\ref{e1})~-- (\ref{e3}).

Для доказательства предложения достаточно показать, что существует рекурсивное множество
полиномиальных недетерминированных машин Тьюринга такое, что его подмножество, состоящее из машинн, распознающих
языки из класса {\bf TFNP},
не является рекурсивно перечислимым.
Поэтому мы ограничимся рассмотрением недетерминированных машин Тьюринга с полиномиальными часами.
Заметим, что в общем случае
полиномиальные часы могут быть реализованы несколькими существенно различными способами.
В частности, полиномиальные часы могут быть реализованы как подпрограмма программы машины Тьюринга,
которая по входу $w$ длины $\vert w \vert =n$ на отдельной ленте вычисляет некоторый фиксированный полином $p(n)$,
записывая на ленту $p(n)$ единиц.
Предполагается, что машина с часами симулирует программу $P$ некоторой машины Тьюринга $M$:
записав на выделенную ленту одну единицу, машина с часами на остальных лентах симулирует
выполнение одной команды программы $P$ на входе $w$. Таким образом, либо
выполнение программы $P$ на входе $w$ естественным образом завершается за $p(n)$ шагов,
либо машина с часами записывает $p(n)$ единиц и принудительно останавливает выполнение программы $P$
в допускающем состоянии.
Возможна реализация полиномиальных часов как внешнего устройства: часы никак не отображаются в программе
машины.
В данной статье мы будем предполагать, что машина Тьюринга ${\frak C}$ с полиномиальными часами имеет две ленты.
Первую ленту машина ${\frak C}$ использует как рабочую. В частности, на первую ленту машина ${\frak C}$ получает вход.
Предполагая, что вход является некоторым словом $w$, длина которого $\vert w \vert$ равна $n$,
на вторую ленту перед началом работы размещается $p(n) \geq n$ единиц.
Считывающее устройство машины ${\frak C}$ перед началом работы размещается на крайний левый символ входа $w$ на первой ленте
и на крайнюю левую единицу на второй ленте. Если считывающее устройство на второй ленте читает единицу,
то выполнение любой команды ведет к смещению вправо на второй ленте. Если на второй ленте читается пустой символ,
то машина ${\frak C}$ останавливается в допускающем состоянии.
Легко понять, что любая машина с полиномиальными часами распознает некоторый язык за полиномиальное
время. Кроме того, любой язык, распознаваемый за полиномиальное время, распознается подходящей машиной с полиномиальными часами.

Доказательство предложения будет основано на сведении от проблемы остановки.
При доказательстве мы будем придерживаться формулировок книги
\cite{Minsky__1967} (см. пункты 8.2, 8.3.1).
Обычно проблема остановки формулируется как задача с двумя входами.

{\sc Проблема остановки (Halt).}

{\sc Дано:} {\it Описание $D({\frak T})$ детерминированной машины Тьюринга ${\frak T}$, вход $w$.}

{\sc Вопрос:} {\it Верно ли, что машина Тьюринга ${\frak T}$ на входе $w$ через конечное число шагов остановится?}

Однако, фиксируя некоторую машину Тьюринга ${\frak T}$, мы можем рассмотреть проблему остановки для
отдельной машины ${\frak T}$.

{\sc Проблема остановки для машины ${\frak T}$ (Halt$({\frak T})$).}

{\sc Дано:} {\it Вход $w$.}

{\sc Вопрос:} {\it Верно ли, что машина Тьюринга ${\frak T}$ на входе $w$ через конечное число шагов остановится?}

Из неразрешимости проблемы {\sc Halt} \cite{Turing__1937} и существования универсальной машины Тьюринга \cite{Turing__1937}
следует неразрешимость проблемы {\sc Halt$({\frak T})$} для некоторой детерминированной машины ${\frak T}$.
Без ограничения общности мы можем предполагать, что машина ${\frak T}$ является  одноленточной
(см., например, \cite{Hopcroft__2000}, пункты  8.4.2, 8.4.3, 9.2.3).
Зафиксируем некоторую одноленточную детерминированную машину Тьюринга ${\frak T}$ с неразрешимой проблемой остановки.
Без ограничения общности мы можем полагать, что машина ${\frak T}$ имеет множество состояний считывающего
устройства (\ref{e1}) и алфавит ленты (\ref{e2}).
Будем полагать, что программа машины ${\frak T}$
задается функцией перехода
\begin{equation}\label{e5}
\tau : (Q \backslash \{ q_1, q_2 \} ) \times \Delta \rightarrow Q \times \Delta \times \{ -1, 0, 1 \}
\end{equation}
и состоит из команд вида
\begin{equation}\label{e6}
q_{i_1}a_{j_{1}} \rightarrow q_{i_2}a_{j_{2}}d,
\end{equation}
где $q_{i_1} \in Q \backslash \{ q_1, q_2 \}$, $q_{i_2} \in Q$, $0 \leq j_{s} \leq m$, $d \in \{-1, 0, 1\}$, $1 \leq s \leq 2$,
определяемых соотношениями
$$\tau (q_{i_1},a_{j_{1}}) =
(q_{i_2},a_{j_{2}},d)$$
по функции перехода (\ref{e5}).
Можно предполагать, что машина ${\frak T}$, начиная работу в состоянии $q_0$, либо через
конечное число шагов переходит в состояние $q_1$ и останавливается, либо работает бесконечно.
Без ограничения общности можно полагать, что все входы машины ${\frak T}$ линейно упорядочены и
образуют последовательность $w_1, w_2, \dots$, где $w_1$~--- пустое слово.
Мы можем полагать, что если $i \geq j$, то $\vert w_i \vert \geq \vert w_j \vert$.
Для произвольного непустого слова $w_t \in \Delta^{\ast}$ в алфавите $\Delta$ мы будем предполагать, что
$w_t=w[t,1]w[t,2] \dots w[t,\vert w_t  \vert]$,
где $w[t,j] \in \Delta$ для всех $1 \leq j \leq \vert w_t  \vert$.

Для произвольного слова $w_t \in \Delta^{\ast}$
определим машину Тьюринга 
$${\frak C}_{w_t} = (Q^{\prime},\Delta,\delta^{\prime})$$ 
с полиномиальными часами, полагая, что
$$Q^{\prime} = Q \cup \{ q_0^{\prime}, q_1^{\prime}, q_2^{\prime}, \dots , q_{\vert w_t \vert +3}^{\prime} \},$$
где $q_0^{\prime}$~--- выделенное начальное состояние,
$q_{-1}^{\prime}$~--- допускающее заключительное состояние,
$q_{1}$~--- отвергающее заключительное состояние,
программа машины ${\frak C}_{w_t}$
состоит из команд
\begin{eqnarray}
&\label{e7}
q_{j-1}^{\prime}x1 \rightarrow q_{j}^{\prime} w[t,j]1 11, 1 \leq j \leq \vert w_t  \vert, t>1, x \in \Delta, \\
&\label{e8}
q_{\vert w_t  \vert}^{\prime}x1 \rightarrow q_{\vert w_t  \vert+1}^{\prime} x1 01, t>1,  x \in \Delta, \\
&\label{e9}
q_{0}^{\prime}x1 \rightarrow q_{1}^{\prime} x1 01, , t=1,  x \in \Delta, \\
&\label{e10}
q_{j}^{\prime}xa_0 \rightarrow q_{-1}^{\prime} xa_0 00, 1 \leq j \leq \vert w_t  \vert, t>1,  x \in \Delta, \\
&\label{e11}
q_{0}^{\prime}xa_0 \rightarrow q_{-1}^{\prime} xa_0 00, t=1,  x \in \Delta, \\
&\label{e12}
q_{\vert w_t  \vert+1}^{\prime}y1 \rightarrow q_{\vert w_t  \vert+1}^{\prime} a_01 11,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e13}
q_{\vert w_t  \vert+1}^{\prime}a_01 \rightarrow q_{\vert w_t  \vert+2}^{\prime} a_01 -11,   t>1, \\
&\label{e14}
q_{\vert w_t  \vert+2}^{\prime}a_01 \rightarrow q_{\vert w_t  \vert+2}^{\prime} a_01 -11,   t>1, \\
&\label{e15}
q_{\vert w_t  \vert+2}^{\prime}y1 \rightarrow q_{\vert w_t  \vert+3}^{\prime} y1 -11,   t>1,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e16}
q_{\vert w_t  \vert+3}^{\prime}y1 \rightarrow q_{\vert w_t  \vert+3}^{\prime} y1 -11,   t>1,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e17}
q_{\vert w_t  \vert+3}^{\prime}a_01 \rightarrow q_{0} a_01 11,   t>1,   \\
&\label{e18}
q_{\vert w_t  \vert+1}^{\prime}a_01 \rightarrow q_{0} a_01 11,   t=1, \\
&\label{e19}
q_{\vert w_t  \vert+1}^{\prime}ya_0 \rightarrow q_{-1}^{\prime} a_0a_0 00,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e20}
q_{\vert w_t  \vert+1}^{\prime}a_0a_0 \rightarrow q_{-1}^{\prime} a_0a_0 00,   t>1, \\
&\label{e21}
q_{\vert w_t  \vert+2}^{\prime}a_0a_0 \rightarrow q_{-1}^{\prime} a_0a_0 00,   t>1, \\
&\label{e22}
q_{\vert w_t  \vert+2}^{\prime}ya_0 \rightarrow q_{-1}^{\prime} ya_0 00,   t>1,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e23}
q_{\vert w_t  \vert+3}^{\prime}ya_0 \rightarrow q_{-1}^{\prime} ya_0 00,   t>1,   y \in \Delta \backslash \{ a_0 \}, \\
&\label{e24}
q_{\vert w_t  \vert+3}^{\prime}a_0a_0 \rightarrow q_{-1}^{\prime} a_0a_0 00,   t>1,   \\
&\label{e25}
q_{\vert w_t  \vert+1}^{\prime}a_0a_0 \rightarrow q_{-1}^{\prime} a_0a_0 00,   t=1.
\end{eqnarray}
Кроме того, для произвольной команды вида (\ref{e7}) машины ${\frak T}$ программа машины ${\frak C}_{w_t}$
содержит команды
\begin{eqnarray}
&\label{e26}
q_{i_1}a_{j_{1}}1 \rightarrow q_{i_2}a_{j_{2}}1d1, \\
&\label{e27}
q_{i_1}a_{j_{1}}a_0 \rightarrow q_{-1}^{\prime} a_0a_0 00.
\end{eqnarray}
Легко понять, что команды (\ref{e7})~-- (\ref{e9}) обеспечивают печать на первой ленте слова $w_t$ и переход
в состояние $q_{\vert w_t  \vert+1}^{\prime}$. Команды (\ref{e12})~-- (\ref{e18})
позволяют стереть первоначальный вход и переводят считывающее устройство в состояние $q_0$,
устанавливая его на крайний левый символ слова $w_t$.
Команды (\ref{e10}), (\ref{e11}), (\ref{e19})~-- (\ref{e25}), (\ref{e27}) обеспечивают работу часов.
Для каждой комбинации символа состояния $q$ и символа первой ленты $a$,
для которой машина ${\frak C}_{w_t}$ может выполнить какую-либо команду,
мы предусматриваем возможность появления символа $a_0$ на второй ленте,
т.е. остановку часов.
Команды (\ref{e26}) позволяют на первой ленте симулировать выполнение программы машины ${\frak T}$
на входе $w_t$ в рамках ограничений часов.
Легко понять, что если машина ${\frak T}$
на входе $w_t$ не останавливается, то машина ${\frak C}_{w_t}$ на всех входах через конечное число шагов
останавливается в допускающем состоянии $q_{-1}^{\prime}$ по часам.
Если машина ${\frak T}$
на входе $w_t$ останавливается, то, начиная с некоторого достаточно большого входа $w$,
машина ${\frak C}_{w_t}$ на всех входах через конечное число шагов
останавливается в отвергающем состоянии $q_{1}$.
Таким образом, машина ${\frak C}_{w_t}$ относится к классу {\bf TFNP} тогда и только тогда, когда
машина ${\frak T}$ на входе $w_t$ не останавливается. Учитывая то, что дополнение языка проблемы остановки
не является рекурсивно перечислимым, отсюда вытекает, что множество машин ${\frak C}_{w_t}$
из класса {\bf TFNP} не является рекурсивно перечислимым.
\end{proof}

Заметим, что машины Тьюринга ${\frak C}_{w_t}$, построенные при доказательстве предложения \ref{TT_04},
являются детерминированными. Поэтому для класса {\bf TFP} всех всюду определенных проблем,
разрешимых за полиномиальное время детерминированными машинами Тьюринга, имеет место следующее утверждение.

\begin{corollary}
\label{TT_05}
Для любого полинома $p(n) \geq n$ множество всех решающих проблемы из класса {\bf TFP} полиномиальных детерминированных машин Тьюринга с часами, ограниченными полиномом $p(n)$, не является рекурсивно перечислимым.
\end{corollary}

Вопрос о том, решает ли машина Тьюринга всюду определенную проблему, весьма близок к равномерной проблеме остановки,
которая может быть сформулирована следующим образом.

{\sc Равномерная проблема остановки (UHalt).}

{\sc Дано:} {\it Описание $D({\frak T})$ детерминированной машины Тьюринга ${\frak T}$.}

{\sc Вопрос:} {\it Верно ли, что машина Тьюринга ${\frak T}$ на любом входе через конечное число шагов переходит в
заключительную конфигурацию?}

В книге \cite{Minsky__1967} (см. пункт 8.3.4)
показано, что проблема {\sc UHalt} неразрешима для одноленточных машин Тьюринга с одним выделенным заключительным состоянием.
Конструкция, рассмотренная при доказательстве предложения \ref{TT_04}, позволяет получить аналог этого утверждения для
полиномиальных машин Тьюринга.

\begin{corollary}
\label{TT_06}
Для любого полинома $p(n) \geq n$ проблема {\sc UHalt} неразрешима на множестве всех
полиномиальных детерминированных машин Тьюринга с часами, ограниченными полиномом $p(n)$.
\end{corollary}

\begin{proof}
Если в программу машины ${\frak C}_{w_t}$ добавить команды
$$q_{1}xy \rightarrow q_{1}xy00, x \in \Delta, y \in \Delta,$$
то машина ${\frak C}_{w_t}$ будет останавливаться на всех входах почасам, если
машина ${\frak T}$ с неразрешимой проблемой остановки на входе $w_t$ не останавливается.
Если машина ${\frak T}$ на входе $w_t$ не останавливается, то, начиная с некоторого достаточно большого входа $w$,
машина ${\frak C}_{w_t}$ будет работать бесконечно на всех входах.
\end{proof}

Традиционный подход к использованию методов защиты информации предполагает применение некоторых фиксированных алгоритмов,
которые известны злоумышленникам. На сегодняшний день в рамках этого подхода известны методы обоснования трудности
лишь в предположении ${\bf P} \not= {\bf NP} \cap \hbox{\bf co-NP}$.
Утверждение предложения \ref{TT_04} является существенным аргументом в пользу того, что класс {\bf TFNP}
не имеет полных проблем, что является принципиальной преградой для более весомого обоснования трудности,
чем то, что можно извлечь из предположения ${\bf P} \not= {\bf NP} \cap \hbox{\bf co-NP}$.

Однако утверждение предложения \ref{TT_04} открывает альтернативную возможность
обоснования трудности задач, связанных с защитой информации. Если алгоритм защиты
не является фиксированным, а выбирается из
некоторого множества $M \subseteq {\bf TFNP}$, то злоумышленнику, решая задачу взлома защиты, необходимо будет, в частности,
решать задачу принадлежности множеству $M$.
С учетом того, что множество {\bf TFNP} не является рекурсивно перечислимым, сложность
задачи принадлежности множеству $M$ может быть, вообще говоря,
настроена на произвольный уровень вплоть до алгоритмической неразрешимости.
При этом высокий уровень надежности системы защиты информации может быть гарантирован даже в том случае,
когда индивидуальные задачи из множества $M$ могут быть решены детерминированными полиномиальными алгоритмами,
т.е. относятся к классу {\bf TFP}. Соответственно, при таком подходе к построению системы защиты информации
трудность взлома сохранится на высоком уровне даже в случае доказательства равенства ${\bf P}={\bf NP}$.


\section*{Заключение}

В данной работе мы установили вычислительную сложность ряда проблем, связанных с нахождением
значений переменных сильно связных компонент булевых функций. В частности, мы показали,
что задача нахождения значений переменных сильно связных компонент булевых функций
не менее трудна, чем решение проблемы выполнимости.
Кроме того, мы рассмотрели вопрос вычислительной трудности задач поиска значений переменных
в том случае, когда известно, что они существуют.
Для этого случая мы показали, что массовая задача нахождения значений переменных для произвольной булевой функции
может быть алгоритмически неразрешимой. В частности, установлено, что для любого полинома $p(n) \geq n$ множество всех решающих проблемы из класса {\bf TFP} полиномиальных детерминированных машин Тьюринга с часами, ограниченными полиномом $p(n)$, не является рекурсивно перечислимым.

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{Crama__Hammer__2011}
Y. Crama, P. L. Hammer,
\href{https://doi.org/10.1017/cbo9780511852008}
{\it Boolean Functions: Theory, Algorithms, and Applications}, Cambridge University Press, Cambridge, 2011.

\bibitem{Hemaspaandra__Narvaez__2021}
L. A. Hemaspaandra, D. E. Narv{\' a}ez,
\href{https://doi.org/10.1007/s13748-021-00234-6}
{\it Existence versus exploitation: the opacity of backdoors and backbones},
Progress in Artificial Intelligence, {\bf 10} (2021),  297--308.

\bibitem{Cheeseman__Kanefsky__1991}
P. Cheeseman, B. Kanefsky, W. M. Taylor,
\href{https://www.dcs.gla.ac.uk/~pat/cpM/papers/cheeseman91where.pdf}{\it Where the really hard problems are}, Proceedings of the 12th international joint conference on Artificial intelligence, {\bf 1} (1991),  331--337.

\bibitem{Mitchell__Selman__1992}
D. Mitchell, B. Selman, H. Levesque,
\href{https://cdn.aaai.org/AAAI/1992/AAAI92-071.pdf}{\it Hard and easy distributions of SAT problems}, Proceedings of the 10th National Conference on Artificial Intelligence, AAAI, 1992,  459--465.

\bibitem{Sleegers__Olij__2000}
J. Sleegers, R. Olij, G. van Horn, D. van den Berg,
\href{https://doi.org/10.1016/j.orp.2020.100160}{\it Where the really hard problems aren’t}, Operations Research Perspectives, {\bf 7} (2000),  100160.

\bibitem{Hartmann__Weigt__2005}
A. K. Hartmann, M. Weigt,
\href{https://doi.org/10.1002/3527606734}{\it Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics}, WILEY-VCH Verlag GmbH \& Co. KGaA, Weinheim, 2005.

\bibitem{Mezard__Montanari__2009}
M. M{\' e}zard, A. Montanari,
\href{https://doi.org/10.1093/acprof:oso/9780198570837.001.0001}{\it Information, Physics, and Computation}, Oxford University Press, New York, 2009.

\bibitem{Moore__Mertens__2011}
C. Moore, S. Mertens,
\href{https://doi.org/10.1093/acprof:oso/9780199233212.001.0001}{\it The Nature of Computation}, Oxford University Press, New York, 2011.

\bibitem{Ding__Sly__2016}
J. Ding, A. Sly, N. Sun,
\href{https://doi.org/10.1007/s00220-015-2492-8}
{\it Satisfiability Threshold for Random Regular NAE-SAT},
Communications in Mathematical Physics, {\bf 341} (2016),  435--489.

\bibitem{Ding__Sly__2022}
J. Ding, A. Sly, N. Sun,
\href{https://doi.org/10.4007/annals.2022.196.1.1}
{\it Proof of the satisfiability conjecture for large k},
Annals of Mathematics, {\bf 196} (2022),  1--388.

\bibitem{Park__Pham__2024}
J. Park, H. T. Pham,
\href{https://doi.org/10.1090/jams/1028}
{\it A proof of the Kahn–Kalai conjecture},
Journal of the American Mathematical Society, {\bf 37} (2024),  235--243.

\bibitem{Park__Vondrak__2024}
B. Park, J. Vondr{\' a}k,
\href{https://doi.org/10.1137/23M1587075}
{\it A Simple Proof of the Nonuniform Kahn~-- Kalai Conjecture},
SIAM Journal on Discrete Mathematics, {\bf 38} (2024).

\bibitem{Kirkpatrick__Toulouse__1985}
S. Kirkpatrick, G. Toulouse,
\href{https://doi.org/10.1051/jphys:019850046080127700}
{\it Configuration space analysis of travelling salesman problems},
Journal de Physique, {\bf 45} (1985) 1277--1292.

\bibitem{Monasson__Zecchina__1996}
R. Monasson, R. Zecchina,
\href{https://doi.org/10.1103/PhysRevLett.76.3881}
{\it Entropy of the K-Satisfiability Problem},
Physical review letters, {\bf 76} (1996) 3881--3885.

\bibitem{Monasson__Zecchina__1997}
R. Monasson, R. Zecchina,
\href{https://doi.org/10.1103/PhysRevE.56.1357}
{\it Statistical mechanics of the random K-satisfiability model},
Physical review E, {\bf 56} (1997) 1357--1370.

\bibitem{Monasson__Zecchina__Kirkpatrick__1999_2}
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky,
\href{https://doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4<414::AID-RSA10>3.0.CO;2-G}
{\it 2+p-SAT: Relation of typical-case complexity to the nature of the phase transition},
Random Structures \& Algorithms, {\bf 15} (1999) 414--435.

\bibitem{Schneider__Froschhammer__Morgenstern__1996}
J. Schneider, C. Froschhammer, I. Morgenstern, T. Husslein, J. M. Singer,
\href{https://doi.org/10.1016/0010-4655(96)00062-8}
{\it Searching for backbonesSearching for backbones~--- an efficient parallel algorithm for the traveling salesman problem},
Computer Physics Communications, {\bf 96} (1996) 173--188.

\bibitem{Monasson__Zecchina__Kirkpatrick__1999}
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky,
\href{https://doi.org/10.1038/22055}
{\it Determining computational complexity from characteristic ‘phase transitions’},
Nature, {\bf 400} (1999) 133--137.

\bibitem{Bollobas__Borgs__Chayes__2001}
B. Bollob{\' a}s, C. Borgs, J. T. Chayes, J. H. Kim, D. B. Wilson,
\href{https://doi.org/10.1002/rsa.1006}
{\it The scaling window of the 2-SAT transition},
Random Structures \& Algorithms, {\bf 18} (2001) 201--256.

\bibitem{Selman__Kirkpatrick__1996}
B. Selman, S. Kirkpatrick,
\href{https://doi.org/10.1016/0004-3702(95)00056-9}
{\it Critical behavior in the computational cost of satisfiability testing},
Artificial Intelligence, {\bf 81} (1996) 273--295.

\bibitem{Childs__Kothari__Ozols__Roetteler__2013}
A. M. Childs, R. Kothari, M. Ozols, M. Roetteler,
\href{https://doi.org/10.4230/LIPIcs.TQC.2013.50}
{\it Easy and Hard Functions for the Boolean Hidden Shift Problem},
8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, Leibniz-Zentrum f{\" u}r Informatik, Schloss Dagstuhl, 2013, 50--79.

\bibitem{Childs__vanDam__2010}
A. M. Childs, W. van Dam,
\href{https://doi.org/10.1103/RevModPhys.82.1}
{\it Quantum algorithms for algebraic problem},
Reviews of Modern Physics, {\bf 82} (2010) 1--52.

\bibitem{Boneh__Lipton__1995}
D. Boneh, R. Lipton,
\href{https://doi.org/10.1007/3-540-44750-4_34}
{\it Quantum cryptanalysis of hidden linear functions},
Lecture Notes in Computer Science, {\bf 963} (1995) 424--437.

\bibitem{Regev__2004}
O. Regev,
\href{https://doi.org/10.1137/S0097539703440678}
{\it Quantum computation and lattice problems},
SIAM Journal on Computing, {\bf 33} (2004) 738--760.

\bibitem{Kuperberg__2005}
G. Kuperberg,
\href{https://doi.org/10.1137/S0097539703436345}
{\it A subexponential-time quantum algorithm for the dihedral hidden subgroup problem},
SIAM Journal on Computing, {\bf 35} (2005) 170--188.

\bibitem{Hallgren__2007}
S. Hallgren,
\href{https://doi.org/10.1145/1206035.1206039}
{\it Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem},
Journal of the ACM, {\bf 54} (2007) 4:1--4:19.

\bibitem{Gaspers__Misra__Ordyniak__Szeider__Zivny__2017}
S. Gaspers, N. Misra, S. Ordyniak, S. Szeider, S. Zivn{\' y},
\href{https://doi.org/10.1016/j.jcss.2016.10.007}
{\it Backdoors into heterogeneous classes of SAT and CSP},
Journal of Computer and System Sciences, {\bf 85} (2017) 38--56.

\bibitem{Samer__Szeider__2008}
M. Samer, S. Szeider,
\href{https://doi.org/10.1007/s10817-008-9114-5}
{\it Backdoor Sets of Quantified Boolean Formulas},
Journal of Automated Reasoning, {\bf 42} (2008) 77--97.

\bibitem{Szeider__2010}
S. Szeider,
\href{https://doi.org/10.3233/SAT190059}
{\it Matched Formulas and Backdoor Sets},
Journal on Satisfiability, Boolean Modelling and Computation, {\bf 6} (2010) 1--12.

\bibitem{AlYahya__Menai__Mathkour__2022}
T. Al-Yahya, M. E. B. A. Menai, H. Mathkour,
\href{https://doi.org/10.3390/a15090302}
{\it Boosting the Performance of CDCL-Based SAT Solvers by Exploiting Backbones and Backdoors},
Algorithms, {\bf 15} (2022) 302.

\bibitem{Menai__Batouche__2006}
M. E. B. Mena\"{\i}, M. Batouche,
\href{https://doi.org/10.1007/11740698_14}
{\it A Backbone-Based Co-evolutionary Heuristic for Partial MAX-SAT},
Lecture Notes in Computer Science, {\bf 3871} (2006) 155--166.

\bibitem{Biere__Faller__Fazekas__2024}
A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks, F. Pollitt,
\href{https://doi.org/10.1007/978-3-031-65627-9_7}
{\it CaDiCaL 2.0},
Lecture Notes in Computer Science, {\bf 14681} (2024) 133--152.

\bibitem{Biere__Jarvisalo__Kiesl__2021}
A. Biere, M. J{\" a}rvisalo, B. Kiesl,
\href{https://doi.org/10.3233/FAIA200992}
{\it Preprocessing in SAT Solving},
Frontiers in Artificial Intelligence and Applications, {\bf 336} (2021) 391--435.

\bibitem{Kirchweger__Szeider__2024}
M. Kirchweger, S. Szeider,
\href{https://doi.org/10.1145/3670405}
{\it SAT Modulo Symmetries for Graph Generation and Enumeration},
ACM Transactions on Computational Logic, {\bf 25} (2024) 1--30.

\bibitem{Heule__Jarvisalo__Biere__2013}
M. J. H. Heule, M. J{\" a}rvisalo, A. Biere,
\href{https://doi.org/10.1007/978-3-642-38171-3_6}
{\it Revisiting Hyper Binary Resolution},
Lecture Notes in Computer Science, {\bf 7874} (2013) 77--93.

\bibitem{Heule__Jarvisalo__Biere__2010}
M. Heule, M. J{\" a}rvisalo, A. Biere,
\href{https://doi.org/10.1007/978-3-642-16242-8_26}
{\it Clause Elimination Procedures for CNF Formulas},
Lecture Notes in Computer Science, {\bf 6397} (2010) 357--371.

\bibitem{Li__2000}
C. M. Li,
\href{https://doi.org/10.1016/S0020-0190(00)00126-5}
{\it Equivalency reasoning to solve a class of hard SAT problems},
Information Processing Letters, {\bf 76} (2000) 75--81.

\bibitem{Vukmirovic__Blanchette__Heule__2023}
P. Vukmirovi{\' c}, J. Blanchette, M. J. H. Heule,
\href{https://doi.org/10.1145/3565366}
{\it SAT-Inspired Eliminations for Superposition},
ACM Transactions on Computational Logic, {\bf 24} (2023) 1--25.

\bibitem{Nishimura__Ragde__Szeider__2005}
N. Nishimura, P. Ragde, S. Szeider,
\href{http://www.satisfiability.org/SAT04/programme/51.pdf}
{\it Detecting backdoor sets with respect to Horn and binary clauses},
Lecture Notes in Computer Science, {\bf 3542} (2005) 96--103.

\bibitem{Dilkina__Gomes__Sabharwal__2014}
B. Dilkina, C. P. Gomes, A. Sabharwal,
\href{https://doi.org/10.1007/s10472-014-9407-9}
{\it Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search},
 Annals of Mathematics and Artificial Intelligence, {\bf 70} (2014) 399--431.

\bibitem{Kilby__Slaney__Thiebaux__Walsh__2005}
P. Kilby, J. Slaney, S. Thiebaux, T. Walsh,
\href{https://cdn.aaai.org/AAAI/2005/AAAI05-217.pdf}
{\it Backbones and backdoors in satisfiability},
Proceedings of the AAAI Conference on Artificial Intelligence, {\bf 20} (2005) 1368--1373.

\bibitem{Hemaspaandra__Narvaez__2021}
L. A. Hemaspaandra, D. E. Narv{\' a}ez,
\href{https://doi.org/10.1007/s13748-021-00234-6}
{\it Existence versus exploitation: the opacity of backdoors and backbones},
Progress in Artificial Intelligence, {\bf 10} (2021) 297--308.

\bibitem{Hemaspaandra__Narvaez__2021_2}
L. A. Hemaspaandra, D. E. Narv{\' a}ez,
\href{https://doi.org/10.1016/j.ic.2021.104772}
{\it The opacity of backbones},
Information and Computation, {\bf 281} (2021) 104772.

%%============================================================

\bibitem{Fowler__Mohammed__Shihab__Broadfoot__2025}
A. Fowler, S. Mohammed, M. Shihab, T. Broadfoot, P. Beerel, C. Sechen, Y. Makris,
\href{https://doi.org/10.46586/tches.v2025.i2.579-603}
{\it A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks},
IACR Transactions on Cryptographic Hardware and Embedded Systems, {\bf 2025} (2025),  579--603.

\bibitem{Lafitte__Nakahara__VanHeule__2014}
F. Lafitte, J. Nakahara Jr., D. Van Heule,
\href{https://doi.org/10.3233/SAT190099}
{\it Applications of SAT Solvers in Cryptanalysis: Finding Weak Keys and Preimages},
Journal on Satisfiability, Boolean Modelling and Computation, {\bf 9} (2014),  1--25.

\bibitem{Shi__Liu__Li__2023}
J. Shi, G. Liu, C. Li,
\href{https://doi.org/10.1049/2023/5323380}
{\it SAT-Based Security Evaluation for WARP against Linear Cryptanalysis},
IET Information Security, {\bf 2023} (2023),  5323380.

\bibitem{Matsui__Cai__2021}
S. Matsui, K. Cai,
\href{https://doi.org/10.1016/j.nahs.2021.101111}
{\it Usability aware secret protection with minimum cost},
Nonlinear Analysis: Hybrid Systems, {\bf 43} (2021),  101111.

\bibitem{Aspvall__Plass__Tarjan__1979}
B. Aspvall, M. F. Plass, R. E. Tarjan,
\href{https://doi.org/10.1016/0020-0190(79)90002-4}
{\it A linear-time algorithm for testing the truth of certain quantified boolean formulas},
Information Processing Letters, {\bf 8} (1979),  121--123.

\bibitem{Tarjan__1972}
R. Tarjan,
\href{https://doi.org/10.1137/0201010}
{\it Depth-First Search and Linear Graph Algorithms},
SIAM Journal on Computing, {\bf 1} (1972),  146--160.

\bibitem{LeBerre__2001}
D. Le Berre,
\href{https://doi.org/10.1016/S1571-0653(04)00314-2}
{\it Exploiting the real power of unit propagation lookahead},
Electronic Notes in Discrete Mathematics, {\bf 9} (2001),  59--80.

\bibitem{Lynce__MarquesSilva__2003}
I. Lynce, J. Marques-Silva,
\href{https://doi.org/10.1109/TAI.2003.1250177}
{\it Probing-based preprocessing techniques for propositional satisfiability},
Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence, IEEE,  Piscataway, 2003.

\bibitem{Sharir__1981}
M. Sharir,
\href{https://doi.org/10.1016/0898-1221(81)90008-0}
{\it A strong-connectivity algorithm and its applications in data flow analysis},
Computers \& Mathematics with Applications, {\bf 7} (1981),  67--72.

\bibitem{Fleischer__Hendrickson__Pinar__2000}
L. K. Fleischer, B. Hendrickson, A. Pinar,
\href{https://doi.org/10.1007/3-540-45591-4_68}
{\it On Identifying Strongly Connected Components in Parallel},
Lecture Notes in Computer Science, {\bf 1800} (2000),  505--511.

\bibitem{Brafman__2004}
R.I. Brafman,
\href{https://doi.org/10.1109/TSMCB.2002.805807}
{\it A simplifier for propositional formulas with many binary clauses},
IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), {\bf 34} (2004),  52--59.

\bibitem{Reeves__Heule__Bryant__2024}
J. E. Reeves, M. J. H. Heule, R. E. Bryant,
\href{https://doi.org/10.1007/978-3-031-65627-9_6}
{\it From Clauses to Klauses},
Lecture Notes in Computer Science, {\bf 14681} (2024),  110--132.

\bibitem{VanGelder__2005}
A. Van Gelder,
\href{https://doi.org/10.1007/s10472-005-0433-5}
{\it Toward leaner binary-clause reasoning in a satisfiability solver},
Annals of Mathematics and Artificial Intelligence, {\bf 43} (2005),  239--253.

\bibitem{Li__2003}
C.-M. Li,
\href{https://doi.org/10.1016/S0166-218X(02)00407-9}
{\it Equivalent literal propagation in the DLL procedure},
Discrete Applied Mathematics, {\bf 130} (2003),  251--276.

\bibitem{Papadimitriou__1994}
C. H. Papadimitriou,
{\it Computational Complexity}, Addison-Wesley Publishing Co. Inc., Boston, 1994.

\bibitem{Biere__Lonsing__Seidl__2011}
A. Biere, F. Lonsing, M. Seidl,
\href{https://doi.org/10.1007/978-3-642-22438-6_10}
{\it Blocked Clause Elimination for QBF},
Lecture Notes in Computer Science, {\bf 6803} (2011),  101--115.

\bibitem{Heule__Kullmann__Marek__2016}
M. J. H. Heule, O. Kullmann, V. W. Marek,
\href{https://doi.org/10.1007/978-3-319-40970-2_15}
{\it Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer},
Lecture Notes in Computer Science, {\bf 9710} (2016),  228--245.

\bibitem{Jarvisalo__Biere__Heule__2010}
M. J{\" a}rvisalo, A. Biere, M. Heule,
\href{https://doi.org/10.1007/978-3-642-12002-2_10}
{\it Blocked Clause Elimination},
Lecture Notes in Computer Science, {\bf 6015} (2010),  129--144.

\bibitem{Fleury__Kaufmann__2024}
M. Fleury, D. Kaufmann,
\href{https://doi.org/10.48550/arXiv.2402.01202}
{\it Life span of SAT techniques},
 arXiv:2402.01202v,  2024.

\bibitem{Subercaseaux__Heule__2023}
B. Subercaseaux, M. J. H. Heule,
\href{https://doi.org/10.1007/978-3-031-30823-9_20}
{\it The Packing Chromatic Number of the Infinite Square Grid is 15},
Lecture Notes in Computer Science, {\bf 13993} (2023),  389--406.

\bibitem{Kiesl__RebolaPardo__Heule__2018}
B. Kiesl, A. Rebola-Pardo, M. J. H. Heule,
\href{https://doi.org/10.1007/978-3-319-94205-6_34}
{\it Extended Resolution Simulates DRAT},
Lecture Notes in Computer Science, {\bf 10900} (2018),  516--531.

\bibitem{Kullmann__1999}
O. Kullmann,
\href{https://doi.org/10.1016/S0166-218X(99)00037-2}
{\it On a generalization of extended resolution},
Discrete Applied Mathematics, {\bf 96-97} (1999),  149--176.

\bibitem{Subercaseaux__2024}
B. Subercaseaux,
\href{https://doi.org/10.29007/p5mc}
{\it Sometimes Hoarding is Harder than Cleaning: NP-hardness of Maximum Blocked-Clause Addition},
EPiC Series in Computing, {\bf 100} (2024),  408--425.

\bibitem{Megiddo__Papadimitriou__1991}
N. Megiddo, C. H. Papadimitriou,
\href{https://doi.org/10.1016/0304-3975(91)90200-L}
{\it On total functions, existence theorems and computational complexity},
Theoretical Computer Science, {\bf 81} (1991),  317--324.

\bibitem{Goldberg__Papadimitriou__2018}
P. W. Goldberg, C. H. Papadimitriou,
\href{https://doi.org/10.1016/j.jcss.2017.12.003}
{\it Towards a unified complexity theory of total functions},
Journal of Computer and System Sciences, {\bf 94} (2018),  167--192.

\bibitem{Goos__Hollender__Jain__Maystre__Pires__Robere__Tao__2024}
M. G{\" o}{\" o}s, A. Hollender, S. Jain, G. Maystre, W. Pires, R. Robere, R. Tao,
\href{https://doi.org/10.1145/3663758}
{\it Separations in Proof Complexity and TFNP},
Journal of the ACM, {\bf 71} (2024),  1--45.

\bibitem{Hartmanis__Stearns__1965}
J. Hartmanis, R. E. Stearns,
\href{https://doi.org/10.2307/1994208}
{\it On the Computational Complexity of Algorithms},
Transactions of the American Mathematical Society, {\bf 117} (1965),  285--306.

\bibitem{Young__1969}
P. R. Young,
\href{https://doi.org/10.1145/321510.321525}
{\it Toward a Theory of Enumerations},
Journal of the ACM, {\bf 16} (1969),  328--348.

\bibitem{Lewis__1970}
F. D. Lewis,
\href{https://doi.org/10.1145/800161.805145}
{\it Unsolvability considerations in computational complexity},
STOC '70: Proceedings of the second annual ACM symposium on Theory of computing,
Association for Computing Machinery, New York,  1970, 22--30.

\bibitem{Borodin__1972}
A. Borodin,
\href{https://doi.org/10.1145/321679.321691}
{\it Computational Complexity and the Existence of Complexity Gaps},
Journal of the ACM, {\bf 19} (1972),  158--174.

\bibitem{Landweber__Robertson__1972}
L. H. Landweber, E. L. Robertson,
\href{https://doi.org/10.1145/321694.321702}
{\it Recursive Properties of Abstract Complexity Classes},
Journal of the ACM, {\bf 19} (1972),  296--308.

\bibitem{Baker__Gill__Solovay__1975}
T. Baker, J. Gill, R. Solovay,
\href{https://doi.org/10.1137/0204037}
{\it Relativizations of the ${\mathcal P} =? {\mathcal NP}$  Question},
SIAM Journal on Computing, {\bf 4} (1975),  431--442.

\bibitem{Ladner__1975}
R. E. Ladner,
\href{https://doi.org/10.1145/321864.321877}
{\it On the Structure of Polynomial Time Reducibility},
Journal of the ACM, {\bf 22} (1975),  155--171.

\bibitem{Landweber__Lipton__Robertson__1981}
L. H. Landweber, R. J. Lipton, E. L. Robertson,
\href{https://doi.org/10.1016/0304-3975(81)90069-4}
{\it On the structure of sets in NP and other complexity classes},
Theoretical Computer Science, {\bf 15} (1981),  181--200.

\bibitem{Chew__Machtey__1981}
P. Chew, M. Machtey,
\href{https://doi.org/10.1016/0022-0000(81)90021-0}
{\it A note on structure and looking back applied to the relative complexity of computable functions},
Journal of Computer and System Sciences, {\bf 22} (1981),  53--59.

\bibitem{Schoning__1982}
U. Sch{\" o}ning,
\href{https://doi.org/10.1016/0304-3975(82)90114-1}
{\it A uniform approach to obtain diagonal sets in complexity classes},
Theoretical Computer Science, {\bf 18} (1982),  95--103.

\bibitem{Kowalczyk__1984}
W. Kowalczyk,
\href{https://link.springer.com/content/pdf/10.1007/BFb0030318.pdf}
{\it Some Connections Between Representability of Complexity Classes and the Power of Formal Systems of Reasonin},
Lecture Notes in Computer Science, {\bf 176} (1984),  364--369.

\bibitem{Hartmanis__Hemachandra__1988}
J. Hartmanis, L. A. Hemachandra,
\href{https://doi.org/10.1016/0304-3975(88)90022-9}
{\it Complexity classes without machines: On complete languages for UP},
Theoretical Computer Science, {\bf 58} (1988),  129--142.

\bibitem{Minsky__1967}
M. L. Minsky,
{\it Computation: finite and infinite machines}, Prentice-Hall, Englewood Cliffs, 1967.

\bibitem{Turing__1937}
A. M. Turing,
\href{https://doi.org/10.1112/plms/s2-42.1.230}
{\it On Computable Numbers, with an Application to the Entscheidungsproblem},
Proceedings of the London Mathematical Society, series 2, {\bf 42} (1936-7),  230--265.

\bibitem{Hopcroft__2000}
J. E. Hopcroft, R. Motwani, J. D. Ullman,
{\it Introduction to Automata Theory, Languages, and Computation}, Addison-Wesley, Boston, 2000.

\end{thebibliography}
\end{document}


