\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{comment}
\usepackage{amsmath, amssymb, amsthm, amstext, mathtools, graphicx, url}
\usepackage{hyperref}

\newif{\ifshowsoln}
\showsolntrue

\begin{document}

\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcommand{\CLIQ}{{\rm CLIQ}}
\newcommand{\FINDCLIQ}{{\rm FINDCLIQ}}
\newcommand{\SCLIQ}{{\rm SCLIQ}}
\newcommand{\bits}[1]{{\{0,1\}^{#1}}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\C}{{\sf C}}
\newcommand{\into}{\rightarrow}
\newcommand{\cvg}{\downarrow}
%\newcommand{\implies}{\rightarrow}
\newcommand{\st}{\mathrel{:}}

\centerline{\bf HW 8 CMSC 452. Morally Due April 23}

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!}


\begin{enumerate}

\item
(30 points)
A {\it poly inequality} is an inequality of the form

$$p(x_1,x_2,\ldots,x_n) \le c$$

where $p(x_1,\ldots,x_n)$ is a polynomial with integer coefficients WITHOUT a constant term, and $c\in \Z$.

TWO EXAMPLES:

$$x_1^3x_4^2 -2x_2x_3 + 18x_3^{14}x_4^2 +x_1 \le 1000.$$

$$x_1 + x_2 \le 89$$

Let POLY PROGRAMMING, called $PP$, be the following problem:

Given a set of poly inequalities
determine if there is some way to set the variables to rationals so that
all the inequalities hold.

\begin{enumerate}
\item
Show that 3-$SAT\le PP$.
\item
Use your reduction on the following formula
(i.e., list the inequalities produced by the reduction)

$$(x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4)\wedge (x_2 \vee \neg x_3 \vee \neg x_4)$$

\end{enumerate}

\centerline{\bf GO TO THE NEXT PAGE!!!!!!!!!!!!}

\newpage



\item
(40 points)
Let
$$\CLIQ17 = \{ G\mid \hbox{ graph $G$ has a clique of size 17 } \}$$

\begin{enumerate}
\item
(25 points)
Either show that CLIQ17 is in P or show that CLIQ17 is NP-complete or do both.
(ALSO --- not to hand in, but think about --- is it likely that
someone in the class will be able to do both?)
\item
(25 points)
Is $\CLIQ17$ closed under minors (see Wikipedia entry for clarification).
That is, if $G \in \CLIQ17$ and $H$ is a minor of $G$, is it necessarily true that $H \in \CLIQ17$?
If so then prove it, if not then give a counterexample.

\url{https://en.wikipedia.org/wiki/Graph_minor}

\end{enumerate}

\item
(30 points) Let
$$FACT = \{ (n,x) \mid \hbox{ there is a nontrivial factor of $n$ that is $\le x$ } \}.$$

(A NONTRIVIAL factor of $n$ is a positive factor that is NOT 1 and NOT $n$.)

$n$ and $x$ are both positive integers and are given in binary, so the NUMBER (say, for example) ONE THOUSAND only takes around 10 bits,
NOT 1000 bits, to input.

Let $FFACT$ be the function that, on input $n$, outputs the complete prime factorization of $n$.

Show that if $FACT\in P$ then $FFACT$ can be computed in Polynomial time.

NOTE- poly in the LENGTH of the input. So the LENGTH of ONE THOUSAND would be TEN.
So $FACT\in P$ means that it takes time $p(\log{n} + \log{x})$ to decide $(n,x)$ for some poly $p$.


\end{enumerate}

\end{document}