Llista de problemes 4

Intruccions

Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:

Vídeos de Sipser

• Lecture 12: Time Complexity
• Lecture 13: P and NP, SAT, poly-time reducibility
• Lecture 15: NP-completeness

Llibres

• (Sipser 2013, \S 7)
• (Hopcroft, Motwani, i Ullman 2007, \S 10 and \S 11.1)

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.

Tots els exercicis

Exercici 1 (Mida de la representació binària)  

1. Demostreu que la mida de la representació binària d’un nombre és logarítmica respecte al mateix nombre. Per ser exactes, demostreu que per a tot mot x \in \{1\}\{0,1\}^*, |x| = \lfloor \log_2(\mathtt{value}_2(x)) \rfloor + 1.
2. Sigui \mathtt{Composite} el llenguatge de tots els nombres (escrits en binari) que són compostos, és a dir, que tenen un factor no trivial. Doneu un algorisme per decidir la pertinença a \mathtt{Composite} i analitzeu el seu temps d’execució en funció de la mida de l’entrada.
3. Sigui \mathtt{Factoring} el llenguatge de tots els parells de nombres (N, k) (escrits en binari) tals que N té un factor no trivial més petit que k. Doneu un algorisme per decidir la pertinença a \mathtt{Factoring} i analitzeu el seu temps d’execució en funció de la mida de l’entrada.
4. Demostreu que tant \mathtt{Composite} com \mathtt{Factoring} pertanyen a \mathbf{NP}.

Recordeu que \mathtt{value}_2(x) representa el nombre obtingut interpretant el mot x com un nombre escrit en base 2. Per exemple, \mathtt{value}_2(110)=0\cdot 2^0+1\cdot 2^1+1\cdot 2^2=2+4=6.

Exercici 2 (Problema del viatjant de comerç) Suposem que se’ns dona una instància del Problema del Viatjant de Comerç (\mathtt{TSP}) amb n ciutats i distàncies d_{ij}. Per a cada subconjunt S de les ciutats excloent la ciutat 1, i per a cada j \in S, definim c[S,j] com el camí més curt que comença a la ciutat 1, visita totes les ciutats de S i acaba a la ciutat j.

1. Doneu un algorisme que calculi c[S,j] mitjançant programació dinàmica, és a dir, progressant de conjunts S més petits a conjunts més grans i utilitzant una definició recurrent de c[S,j]. Mostreu que aquest algoritme resol el \mathtt{TSP} en temps O(n^2 2^n). Quins són els requeriments d’espai de l’algoritme?

2. Suposem que volem trobar el camí més curt (en el sentit de la suma dels pesos) de 1 a n, sense necessitat de visitar totes les ciutats. Argumenteu per què aquest problema es pot resoldre en temps polinòmic.

Exercici 3 (A la recerca de cliques) Una k-clica en un graf G = (V,E) és un subgraf complet d’ordre k de G, és a dir, un subgraf de k vèrtexs que conté totes les arestes possibles entre ells. Diem que G' és una clica en G si G' és una k-clica en G per a algun k. Recordeu que el problema següent és un NP-complet conegut. \mathtt{Clica}\text{: Donat un graf no dirigit $G$ i un natural $k$, determinar si $G$ conté una $k$-clica.}

Els següents són alguns problemes relacionats amb \mathtt{Clica}.

1. Clica maximal. Una clica és maximal si no es pot estendre, és a dir, si no hi ha cap clica més gran que la contingui. Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica maximal de G. Quin és el cost de l’algorisme?

2. Clica màxima. Una clica és màxima si no hi ha cap altra clica que tingui més vèrtexs (una clica màxima sempre és maximal però la inclusió inversa no sempre és certa). Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica màxima de G. Quin és el cost de l’algorisme?

3. Clica planar. Recordeu que un graf és planar si es pot dibuixar en el pla sense creuaments d’arestes. Sigui \mathtt{Clica Planar} el problema següent: donat un graf planar no dirigit G i un natural k, té G una k-clica? Demostreu que \mathtt{Clica Planar} té un algorisme de temps polinòmic.

   Nota

   La comprovació de la planaritat es pot fer en temps lineal (en el nombre de vèrtexs). Podeu assumir l’existència d’aquests algorismes per l’exercici.

4. Mitja clica. Sigui \mathtt{Mitja Clica} el problema següent: donat un graf no dirigit G, té G una clica amb almenys \big\lceil \frac{|V(G)|}{2} \big\rceil vèrtexs? Demostreu que \mathtt{Mitja Clica} és \mathbf{NP}-complet.

Exercici 4 (Propietats de tancament de \mathbf{P}, \mathbf{NP} i \mathbf{coNP}) L’objectiu d’aquest exercici és revisar algunes propietats de tancament de \mathbf{P}, \mathbf{NP} i \mathbf{coNP}.

1. (propietat de tancament respecte de la unió) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cup B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cup B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cup B\in \mathbf{coNP}.
2. (propietat de tancament respecte de la intersecció) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cap B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cap B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cap B\in \mathbf{coNP}.
3. (propietat de tancament respecte de la concatenació) Demostreu les implicacions següents:
   1. Donats A i B a \mathbf{P}, A\cdot B\in \mathbf{P}.
      
   2. Donats A i B a \mathbf{NP}, A\cdot B\in \mathbf{NP}.
      
   3. Donats A i B a \mathbf{coNP}, A\cdot B\in \mathbf{coNP}.

Exercici 5 (Reduccions de temps polinòmic) Considereu la relació \le_m^p entre llenguatges i justifiqueu les respostes a les preguntes següents.

1. És \le_m^p reflexiva? És a dir, es compleix que A \le_m^p A per a qualsevol llenguatge A?

2. És \le_m^p simètrica? És a dir, es compleix que si A \le_m^p B, aleshores B \le_m^p A per a qualssevol llenguatges A, B?

3. És \le_m^p antisimètrica? És a dir, es compleix que A \le_m^p B i B \le_m^p A impliquen A = B per a qualssevol llenguatges A, B?

4. És \le_m^p transitiva? És a dir, es compleix que A \le_m^p B i B \le_m^p C impliquen A \le_m^p C per a qualssevol llenguatges A, B i C?

Reduccions polinomiques \leq_m^p

Recordeu que, donats dos llenguatges A, B sobre el mateix alfabet \Sigma, diem que A es redueix polinòmicamente a B (s’escriu A\leq_m^p B o A \leq_p B) si existeix una funció total f:\Sigma^*\to\Sigma^* computable en temps polinòmic tal que per a tot w\in \Sigma^*, w\in A si i només si f(w)\in B.

Una propietat útil és el tancament de les classes \mathbf{P}, \mathbf{NP} i \mathbf{coNP} per reduccions polinòmiques, és a dir, donat A\leq_m^p B,

• si B\in \mathbf{P}, llavors A\in \mathbf{P},
• si B\in \mathbf{NP}, llavors A\in \mathbf{NP}, i
• si B\in \mathbf{coNP}, llavors A\in \mathbf{coNP}.

La m en la notació \leq_m^p indica que la funció f no és necessàriament injectiva (és many-one).

Exercici 6 (Tancament per l’estrella de Kleene)  

1. Mostreu que \mathbf{P} és tancada per l’estrella de Kleene.

   Consell

   Utilitzeu programació dinàmica. Donat un conjunt A \in \mathbf{P} sobre \Sigma i una entrada x = x_1 \dots x_n amb x_i \in \Sigma, construïu una taula que indiqui per a cada i < j si el submot x_i \dots x_j és a A^*.

2. Mostreu que \mathbf{NP} és tancada per l’estrella de Kleene.

Exercici 7 (Cerca vs decisió) Demostreu les conseqüències següents de la hipòtesi \mathbf{P} = \mathbf{NP}.

1. Existeix un algorisme de temps polinòmic que produeix un model (una assignació que satisfà la fórmula) quan se li dóna una fórmula booleana satisfactible.

2. Els enters es poden factoritzar en temps polinòmic.

3. Hi ha un algorisme de temps polinòmic que pren com a entrada un graf no dirigit i troba una clica màxima continguda en aquest graf.

Nota

Els algorismes que se us demana proporcionar calculen una funció, però \mathbf{NP} conté llenguatges, no funcions. L’assumpció \mathbf{P} = \mathbf{NP} implica que decidir satisfactibilitat, no primalitat i l’existència de cliques d’una mida donada és resoluble en temps polinòmic. Però, encara que l’assumpció no mostra com trobar les solucions, heu de demostrar que es poden trobar igualment.

Exercici 8 (Teorema de Berman) Un llenguatge s’anomena unari si cada mot que conté és de la forma 1^n per a algun n \ge 0.

Demostreu el teorema de Berman (1978): si un llenguatge unari és \mathbf{NP}-complet, aleshores \mathbf{P} = \mathbf{NP}.

Consell

Utilitzeu el fet que \mathtt{SAT} és \mathbf{NP}-complet i, per hipòtesi, reductible a un llenguatge unari mitjançant una funció f. Per decidir \mathtt{SAT}, donada una fórmula booleana d’entrada \phi, considereu l’arbre on l’arrel (nivell 0) és \phi i les fórmules al nivell k s’obtenen de les del nivell k-1 de manera que la k-èsima variable pren els 2 valors de veritat possibles. Demostreu com f permet explorar aquest arbre en temps polòmic.

Exercici 9 (\mathbf{NP} i \mathtt{HALT}) Demostreu que \mathtt{HALT} és \mathbf{NP}-difícil. És també \mathbf{NP}-complet?

Nota

Recordeu que \mathtt{HALT}=\{\langle x,y \rangle \mid M_x(y)\!\downarrow\}, on M_x és la màquina de Turing amb nombre de Gödel x i el símbol \downarrow indica que la màquina finalitza.

Exercici 10 (\mathtt{UniqueSAT}) La classe \mathbf{DP} (de difference polynomial time) es defineix com el conjunt de llenguatges L per als quals existeixen dos llenguatges L_1 \in \mathbf{NP}, L_2 \in \mathbf{coNP} tals que L = L_1 \cap L_2. Cal notar que, com que \overline{L_2} \in \mathbf{NP}, L és la diferència de dos conjunts de \mathbf{NP} (però no confongueu \mathbf{DP} amb \mathbf{NP} \cap \mathbf{coNP}, que s’assembla superficialment).

Considereu el problema \mathtt{Unique SAT}, que consisteix a determinar si una fórmula booleana té una única assignació satisfactible (o model) i demostreu els següents fets.

1. \mathtt{Unique SAT} \in \mathbf{DP}.
   
2. Si \mathtt{Unique SAT} és a \mathbf{NP}, aleshores \mathbf{NP} = \mathbf{coNP}.

Exercici 11 (Pertanyen a \mathbf{P}?) Demostreu que els llenguatges següents sobre grafs no dirigits són a \mathbf{NP}. Quins pertanyen a \mathbf{P}?

1. Dos coloració. \mathtt{2COL} = \{ G \mid el graf G té una 2-coloració\}, on una k-coloració de G és una assignació d’un nombre a \{1,\dots,k\} a cada vèrtex de G tal que tot parell de vèrtexs adjacents rep colors diferents.
2. Tres coloració. \mathtt{3COL} = \{ G \mid el graf G té una 3-coloració\}.
3. Camí hamiltonià. \mathtt{HP} = \{ G \mid el graf G té un camí hamiltonià\}, on un camí se’n diu hamiltonià si visita cada vèrtex exactament un cop.
4. Connectivitat. \mathtt{CONNECTED} =\{ G \mid G és un graf connex\}.

Exercici 12 (Representació de llenguatges sobre un alfabet binari) Siguin A i B dos llenguatges sobre el mateix alfabet \Sigma, i sigui e : \Sigma \to \{0,1\}^k una funció injectiva que assigna a cada símbol de \Sigma una cadena binària de longitud k. Per a una cadena x=x_1x_2\cdots x_n \in \Sigma^*, definim la codificació de x com e^+(x) = e(x_1)e(x_2)\cdots e(x_n) de longitud k\cdot n, és a dir, la cadena on cada símbol de x és transformat segons e. Siguin A'=\{e^+(x) \mid x\in A\} i B'=\{e^+(x) \mid x\in B\}.

Demostreu les afirmacions següents:

1. El llenguatge A és a \mathbf{P} si i només si el llenguatge A' és a \mathbf{P}.
2. El llenguatge A és a \mathbf{NP} si i només si el llenguatge A' és a \mathbf{NP}.
3. El llenguatge A és a \mathbf{coNP} si i només si el llenguatge A' és a \mathbf{coNP}.
4. A\leq_m^p B si i només si A'\leq_m^p B'.

Exercici 13 (Suma de subconjunts / Motxilla) Per a n\in \mathbb N, sigui [n]=\{1,\dots,n\}. Considerem els llenguatges següents.

\texttt{SUBSET-SUM}=\left\{\langle c, x_1, \ldots, x_n\rangle :\ \begin{array}{c} c, x_1, \ldots, x_n\in \mathbb N \text{ i } \\ \exists S \subseteq [n]\ \sum_{i \in S} x_i = c\end{array}\right\}

\texttt{SUBSET-SUM-INT}=\left\{\langle c_1, c_2, x_1, \ldots, x_n\rangle :\ \begin{array}{c} c_1, c_2, x_1, \ldots, x_n\in \mathbb N \text{ i } \\ \exists S \subseteq [n]\ c_1\leq \sum_{i \in S} x_i \leq c_2\end{array}\right\}

\texttt{KNAPSACK}=\left\{\langle w_1, \ldots, w_n, v_1, \ldots, v_n, W, V\rangle :\ \begin{array}{c} w_1, \ldots, w_n, v_1, \ldots, v_n, W, V\in \mathbb N \text{ i } \\ \exists S \subseteq [n]\ \sum_{i \in S} w_i \leq W \text{ i } \sum_{i \in S} v_i \geq V\end{array}\right\}

Si no s’indica el contrari, en els exercicis següents assumim que l’entrada es dona en binari.

1. Demostreu que si l’entrada es dona en unari, aleshores \texttt{SUBSET-SUM} es pot resoldre en temps polinòmic. (Pista: utilitzeu programació dinàmica.)
   
2. Demostreu que si l’entrada es dona en unari, aleshores \texttt{KNAPSACK} es pot resoldre en temps polinòmic. (Pista: utilitzeu programació dinàmica.)
   
3. Demostreu que \texttt{SUBSET-SUM} és \mathbf{NP}-complet. (Pista: reduïu des de \texttt{3-SAT}.)
   
4. Demostreu que \texttt{KNAPSACK} és \mathbf{NP}-complet.
5. Demostreu que \texttt{SUBSET-SUM-INT} és \mathbf{NP}-complet.

Exercici 14 (Sistemes de demostració) Un sistema de demostració per a un llenguatge L \subseteq \{0,1\}^* és una funció computable en temps polinòmic P : \{0,1\}^* \to L.

Un sistema de demostració P està fitat polinòmicament si existeix un polinomi p tal que per a tot x \in L, existeix un mot w de mida màxima p(|x|) tal que P(w) = x. Es pot pensar en w com una demostració del fet que x \in L i estar fitat polinòmicament vol dir que tot x \in L té una demostració de mida polinòmica.

1. Demostreu que un llenguatge no buit L és a \mathbf{NP} si i només si existeix un sistema de demostració per a L fitat polinòmicament.

2. Demostreu que si existeix un sistema de demostració fitat polinòmicament per a \texttt{TAUT}, aleshores \mathbf{NP} = \mathbf{coNP}.

3. Quan P i P' són dos sistemes de demostració per al mateix llenguatge L, diem que P' simula P si existeix un polinomi p tal que per a tot w \in \{0,1\}^*, existeix un mot w' tal que P'(w') = P(w) i |w'| \leq p(|w|). Demostreu que si P és un sistema de demostració per a L fitat polinòmicament i P' simula P, aleshores P' també està fitat polinòmicament.

Nota

Recordeu que \texttt{TAUT} = \{\langle \varphi \rangle : \varphi \text{ és una fórmula booleana en DNF i una tautologia}\}.

Exercici 15 (Padding i el teorema de Ladner) L’objectiu d’aquest exercici guiat és veure els primers passos necessaris per demostrar el teorema de Ladner, és a dir, l’afirmació següent: si \mathbf{P}\neq \mathbf{NP}, aleshores existeix un llenguatge L tal que L\in \mathbf{NP}\setminus \mathbf{P} i L no és \mathbf{NP}-complet.

Donades dues cadenes booleanes w,z, amb w\circ z denotem la seva concatenació. Recordeu que \mathtt{SAT} (el problema de satisfactibilitat booleana) consisteix a determinar si existeix una assignació de valors True/False que satisfà una fórmula booleana donada.

1. Sigui \mathtt{SAT}'=\{ \varphi\circ 1^{2^n} : |\varphi|=n \land \varphi\in \mathtt{SAT} \}. Demostreu que \mathtt{SAT}' és a \mathbf{P}.

2. Sigui \mathtt{SAT}^{\prime\prime}=\{ \varphi\circ 1^{n^c} : |\varphi|=n \land \varphi\in \mathtt{SAT} \}, on c és una constant. Demostreu que \mathtt{SAT}^{\prime\prime} és \mathbf{NP}-complet.

3. Per a qualsevol funció H(n), sigui \mathtt{SAT}_H=\{ \varphi\circ 1^{H(n)} : |\varphi|=n \land \varphi\in \mathtt{SAT} \}. Demostreu que \mathtt{SAT}_H és a \mathbf{NP}.

4. A la resta de l’exercici ens centrem en una funció H concreta. Sigui H(n) el menor nombre natural i\leq \log\log n tal que la MT M_i resol x\in \mathtt{SAT}_H en temps i|x|^i, per a totes les entrades x\in \{0,1\}^* amb |x|\leq \log n. Si no existeix tal i, definim H(n)=\log\log n.

   1. H(n) està definida fent referència a si mateixa; tanmateix, aquesta definició no és cíclica. És a dir, demostreu que H(n) està ben definida.

   2. Demostreu que, si \mathtt{SAT}_H\in \mathbf{P}, aleshores existeix una constant c tal que H(n)\leq c per a tot n.

   3. Demostreu que, si \mathtt{SAT}_H\in \mathbf{P}, aleshores \mathtt{SAT}\leq_p \mathtt{SAT}_H i, per tant, \mathbf{P}=\mathbf{NP}.

Per demostrar el teorema de Ladner, només resta argumentar que si \mathtt{SAT}_H fos \mathbf{NP}-complet, aleshores \mathtt{SAT}\in \mathbf{P} (això és una mica més tècnic i queda fora de l’abast d’aquest exercici).

Posant-ho tot plegat, si \mathbf{P}\neq \mathbf{NP}, aleshores \mathtt{SAT}_H és un llenguatge a \mathbf{NP}\setminus \mathbf{P} que no és \mathbf{NP}-complet.

Exercici 16 (Oracles) Una màquina de Turing amb oracle és una màquina de Turing M amb una cinta especial anomenada cinta d’oracle i tres estats especials q_{query}, q_{yes} i q_{no}. Per executar M, a més de l’entrada, especifiquem un llenguatge O\subseteq \{0,1\}^* que s’utilitza com a oracle per a M. Sempre que durant l’execució M entra en l’estat q_{query}, el contingut de la cinta d’oracle s’interpreta com una consulta a l’oracle O i, en un pas, M transiciona a q_{yes} si x\in O i a q_{no} en cas contrari. Si M és una màquina de Turing amb oracle, O \subseteq \{0,1\}^* un llenguatge i x \in \{0,1\}^*, llavors denotem la sortida de M amb entrada x i oracle O amb M(x)^O. Les màquines de Turing indeterministes amb oracle es defineixen de manera anàloga.

Per a qualsevol O \subseteq \{0,1\}^*, \mathbf{P}^O és la classe de llenguatges que poden ser decidits per màquines de Turing deterministes amb accés a l’oracle O en temps polinòmic i \mathbf{NP}^O es defineix de manera anàloga per a màquines de Turing indeterministes amb oracle. Donada una classe {\cal C} de llenguatges, escrivim \mathbf{P}^{\cal C} = \bigcup_{O \in {\cal C}} \mathbf{P}^O i \mathbf{NP}^{\cal C} = \bigcup_{O \in {\cal C}} \mathbf{NP}^O.

1. Demostreu que per a tot oracle O\in \mathbf{P}, \mathbf{P}^O = \mathbf{P}.
2. Demostreu que \mathbf{NP} \cup \mathbf{coNP}\subseteq \mathbf{P}^{\mathtt{SAT}}.
3. Definim el llenguatge \mathtt{EXPCOM} = \{(M,x,1^N) \mid M és una màquina de Turing determinista que accepta x en un màxim de 2^N passes\}. Demostreu que \mathbf{P}^{\mathtt{EXPCOM}} = \mathbf{NP}^{\mathtt{EXPCOM}} = \mathbf{EXP}.
4. Demostreu que \mathbf{NP}^{\mathbf{NP} \cap \mathbf{coNP}} = \mathbf{NP}.

El teorema de Baker-Gill-Solovay estableix que existeixen oracles A i B tals que \mathbf{P}^A = \mathbf{NP}^A i \mathbf{P}^B \neq \mathbf{NP}^B. Això mostra que la qüestió de si \mathbf{P} = \mathbf{NP} no es pot resoldre mitjançant tècniques que relativitzen, és a dir, tècniques que funcionen per a tots els oracles, com ara la diagonalització.