\documentclass[12pt]{article}

\usepackage{fullpage,amsfonts,amsmath,amssymb,amstext,amsthm,graphicx}


%%% In this file, replace capitalized parts with your information and fill in the blanks. 

\title{SAT solver performance on MY PROBLEM}
\author{LIST YOUR GROUP MEMBERS HERE}

\date{}

\begin{document}


\maketitle


%%%% In the first section, describe where your problem is coming from. Below is an example for e.g. 

\section{Introduction}

The problem MYPROBLEM is defined as follows:   %%% REPLACE KNAPSACK WITH YOUR PROBLEM BELOW 


\paragraph{GKD}  (General Knapsack Decision Problem).\\
\underline{Instance:}\\
$\langle (w_1,p_1),\cdots,(w_n,p_n),B,P\rangle$
(with all integers nonnegative represented in binary).\\
\underline{Acceptance Condition:}\\
Accept  if there is an $S\subseteq\{1,\cdots,n\}$ such that $\sum_{i\in S}w_i \leq B$ and $\sum_{i\in S}p_i \geq P$. \\

%%% Write a paragraph or two about your problem: 

This is an important problem ...   It was proven to be NP-complete by  Karp in \cite{karp1972reducibility}...  

%%% Describe this project: the goal, steps of the project, the results you got, etc. 


\section{Reducing   MYPROBLEM to SAT} 


%%% BASED ON  YOUR MILESTONE 2 SUBMISSION

 %%% START BY DEFINING THE SAT PROBLEM YOU ARE REDUCING TO 
 
 %%%   THEN PROCEED EXPLAINING YOUR REDUCTION

We reduce MYPROBLEM to SAT as follows: 

\paragraph{Variables:}  

\paragraph{Constraints: } 



\section{Generating random instances of MYPROBLEM} 

%%% BASED ON  YOUR MILESTONE 4 SUBMISSION 


\section{Experimental results} 



%%% First say which solver and system you use for your experiments (from Milestone 3)  



%%% Then say for which range of parameters you generated random instances 


%%%  Then include and  explain the average performance of  the solver on these instances as a function of your problem size (usually $n$) 


%\begin{figure}

%\includegraphics{myplot} 

%\caption{HERE IS THE PLOT}  %% replace with description of your graph 

 %\end{figure} 


%%% Explain what you think the dependence of the run time of the solver on n is.  
%%% You can use curve-fitting tool of Matlab, etc, to see if you can at least distinguish if it is likely to be  linear, quadratic, exponential, etc. 
%%% Here you can also discuss how many of instances were satisfiable vs. unsatisfiable, and whether there was a difference in performance between those.  


\section{Additional experiments} 

%%% Here, describe  the additional work you have done.  


\section{Conclusion} 

%%% Talk about the ranges of parameters you used, whether solvers did well or not, etc. 

%%%% Create a bibliography file (e.g. comp6902.bib) and insert the references in that file in bibtex format.  
%%%% Usually when you search for a reference on Google, etc, you have an option of downloading the reference in bibtex format under "cite". 

\bibliographystyle{alpha}
\bibliography{comp6902}


\end{document} 