\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage[round]{natbib}
\let\cite\citep
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
% Use this header.tex file for:
% 1. frontmatter/preamble LaTeX definitions
% - Example: \usepackage{xspace}
% 2. global macros available in all document blocks
% - Example: \def\example{This is an example macro.}
%
% You should ONLY add such definitions in this header.tex space,
% and treat the main article content as the body/mainmatter of your document
% Preamble-only macros such as \documentclass and \usepackage are
% NOT allowed in the main document, and definitions will be local to the current block.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[definition]{definition}
\date{}
\begin{document}
\title{Recurrences and Algorithm for Counting and Generating Circuit Layouts}
\author[1]{Rui-Jie Fang}%
\affil[1]{Germantown Friends School}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\sloppy
\section*{Introduction}
{\label{743976}}
A resistor circuit is a circuit with $n$ resistors and a single voltage source.
The problem of counting resistor layouts is as follows:
Given a set of $n$ resistors $R$ each with resistance $R_k$, $i \leq k \leq n$,
a voltage $\varepsilon$, and a current $I_{eq}$,
find a resistor layout with a single voltage source $\varepsilon$
that satisfies $I_{eq}$. Based on this basic formulation, we can
also ask the following:
\begin{enumerate}
\item Does an efficient algorithm
exist for this problem?
\item Can we give an algorithm that
generates all n-resistor layouts without any
constraints?
\item Based on 2) , can we count the total
amount of resistor layouts for any n?
\end{enumerate}
We first show a proof that
the problem of generating resistor layouts that reach a
specific equivalent resistance is $\mathbf{NP}$-complete
by a reduction to the subset sum problem. Following
the intuition for the reduction for subset sums, we
show a recurrence for counting the total amount of
resistor layouts for any n and a related algorithm for
generating all such layouts.
\section*{NP-Completeness Proof}
{\label{320527}}\par\null\par\null
We prove that the following problem ($X$) is NP-complete.\\
\textbf{Problem (Generating a Layout to Reach a Given Resistence).} Given a set of n
resistors $R$ each with resistance $R_k$,$i [?] k [?] n$, a voltage $\varepsilon$, and a
current $I_eq$, find a resistor layout $G(R) = (R,P)$ (where $R$ is the set of resistors
and $P$ is the set of operators) using all resistors in R with a single voltage source $\varepsilon$ that satisfies $I_eq$.\\
Recall the subset sum problem ($Y$):\\
\textbf{Problem (Subset Sum).} [KlTa] Given natural numbers $w_{1...n}$ and a target number $W$,
is there a subset of $w_{1},...,w_n$ that adds up to precisely $W$?\\
\begin{lemma}
$X \in \mathbf{NP}$.
\end{lemma}
\begin{proof}
Both serial and parallel formulas for equivalent resistance ($R_{serial} = \sum_i Ri$,
$R_{parallel} = 1/\sum_i \frac{1}{R_i}$) can be evaluated in $O(n)$ time as they are simple
summations. Since $G(R)$ contains only parallel and serial resistors, it can also be
calculated in $O(n)$ time since any k-resistor component can be calculated in $O(k)$
time.
\end{proof}
\begin{theorem}
$X \leq _p Y$.
\end{theorem}
\begin{proof}
Define a formula for computing equivalent resistence
$$Req(R) =\sum_i S_i +sum_i P_i$$
where $S$ is a set of resistors in series and $P$ is a set of resistors in parallel.
Note that $P_i = S' \cup P'$ for some smaller partition $S'$ and $P'$. In other words, we can partition $P$ recursively into $\Omega{2^{|P|}}$ subsets which generates a different Req(R) for
each P.
Since there are $n$ (not accounting all permutations) distinct formulations of $S$
and $P$ and $\Omega(2^n)$ distinct formulations for P, there are in total $n+\Omega(2^n)$)
different ways of getting a distinct $R_{eq}(R)$. Problem $X$ asks if there exists
$R_{eq}(R)\cdot I_{eq} = \varepsilon$, $R_{eq}(R) = \varepsilon /I_{eq}$.
Since we are essentially asking if there exists
$R_{eq}(R) = W$ for some number $W$ and $R_{eq}(R)$ depends on sets $S, P \in R$ that have a
lower bound of distinct partitions $n +\Omega(2^n) \geq O(2^n)$ in total number of subsets for
$w_{1...n}$. Therefore, theorem 2 holds.
\end{proof}
\section*{A Recursive Data Structure for Representing Resistor
Circuits}
{\label{307082}}\par\null
We provide a top-down recursive algorithm that generates all $n$-resistor circuit layouts using the data structure presented above. We first define two concepts:
\begin{definition}{stuff}
\end{definition}
The algorithm backtracks all possible placement of the $n$-th resistor before placing the ones after it. The algorithm is analogous to breadth-first-search with the ability to generate extra candidate solutions to the right of the tree.\\
\section*{An Algorithm for Generating All Circuit
Layouts}
{\label{342066}}\par\null\par\null
\section*{Bounding the Total Number of Circuit
Layouts}
{\label{920552}}\par\null
\section*{Future Work}
{\label{449546}}\par\null
\textbf{Acknowledgements}
\selectlanguage{english}
\FloatBarrier
\end{document}