×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## COMPUTER VISION SYSTEMS

by: Khalil Conroy

14

0

3

# COMPUTER VISION SYSTEMS CAP 6411

Khalil Conroy
University of Central Florida
GPA 3.76

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
3
WORDS
KARMA
25 ?

## Popular in System Engineering

This 3 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 6411 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/227217/cap-6411-university-of-central-florida in System Engineering at University of Central Florida.

×

## Reviews for COMPUTER VISION SYSTEMS

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
PARTITION INTO GLOBAL DEFENSIVE ALLIANCESPGDA is NPComplete NOT ALL EQUAL 3SAT NAE3SAT Input A set U u1u2un of variables and a collection C C C Cm of clauses 1 2 over U where each clause contains exactly three literals variables or their complements with no literal appearing more than once in any given clause Question Is there a truth assignment that makes one or two but not all three literals true in each clause We may assume that each literal appears in at least one of the clauses otherwise for each literal u j that does not appear in any of the clauses we can add another variable y and two clauses C u jy and C u j7 These two clauses are satis ed by any truth assignment and do not affect the truth assignment of the original problem Theorem Given a graph G the problem of deciding whether the graph G has a partition into global defensive alliances is NP Complete Proof Given an instance of NAE3SAT with n variables and m clauses we transform it into an instance of PGDA by constructing a graph G VE as follows For a literal u e U U U let Cu be the set of clauses that contains u Let V QUXURUT where Qquue ULJU X xllSi S n R U atU5 Ru and T U ISjSmTJ For all u e U Ru r ul Si S 2 and for all e U Ru i3 ul Si S Also for all C e C T If atj btj 0M C 61 bc For each literal u e U UU we create a star Su where VSu qu URu and the vertex qu forms the center of the star For each x e X we add edges xlqu1 and xlqt71 in graph G For each clause C e C we setup atriangle T in V and for each vertex t ue T add an edge qu tj in graph G The order of the constructed graph V 5n 6m and the size ofthe graph E 4n 9m which is polynomially related to the size of NAE3SAT problem We now claim that the constructed graph G has a partition into global defensive alliances if and only if the given instance of NAE3SAT has a satisfying truth assignment The proof of the claim is as follows 3 Suppose that the given instance of NAE3SAT has a satisfying truth assignment f U gt 01 We define a partition ofthe vertex set V A1 UA2 as follows A UEMAfutlqu U x l u e U U R07 N US it u o T l and A2 V A We now show that bothA1 and A2 are global defensive alliances in graph G Consider any ve Ar 6 12 and consider five cases Case 1 v qu for some u e U From the partitioning scheme Nv m A x U LJISJSM t u m T ie Nv WA 1Cu X Similarly Nvn V A Ru ie Nvn V A 2 Cu NvmA 2 NvmV A 1 Case 2 v qu for some u e U Again from the partitioning scheme Nv m A U15 t u m T ie Nv WA C14 Nv V ARu ie Nv V A C14 NvmA 2 NvnV A 1 Case 3 ve Ru for some u e U U U Then by construction and partitioning scheme Nv NA Q and Nv m V A qu Hence NvmA 2 NvmV A 1 Case 4 v x Then Nv NA qu and Nv V A qt7 Hence NvmA 2 NvnV A 1 Case 5 v t u for some u e U U U By construction and partitioning scheme N v WA 2 qu and by the property of satisfying truth assignment of NAE3SAT Nvm V Ag T t u Hence Nv A 2 Nv V A 1 Hence Similarly Hence Since for all v e A where r 6 12 Nv WA 2 Nv V A X 1 A is a defensive alliance It is also easy to see that NA V Hence both A1 and A2 are global defensive alliances and they partition the vertex set of graph G lt Suppose now that the constructed graph G has a vertex partition A1A2 such that both A1 and A2 are global defensive alliances Since each vertex x e X is adjacent to only two vertices qu and q exactly one of these vertices must be in the same set A r 6 01 otherwise NV A g V x which is contrary to V A being a global defensive alliance Suppose that qu e A for some u e U UU and r 6 01 It is easy to see that Ru 0 A Q Suppose to the contrary and let w e Ru A Since Nw qu wg A NV A g V w which is contrary to V A being a global defensive alliance This also implies that for all qu e A Nqu V A Q Ru Consider two cases Rm 2 Since Nqu 2 Cu Case 1 u e U then by construction Cu X 2 Thus by above implication we NQWDoW A dm have 4 and since A is a defensive alliance we must have N W lo A N W 1 Ru qu x U Us in u o T 1 Ru1 Cu11 Also by Case 1 x e Nqu1 V Ar Thus Nqu1 V Ar 2 C11 Nqul 2 Cul 2 and since A is a defensive alliance we must have N W lo A N W lRu x qu U Us in u o T 1 Case 2 u e 17 then by construction 1 Since The above arguments show the following lemma Lemma 1 For all u e U U17 ifqu1e A for re 01 then for all tju1e T 13 Smtju1eAr We now define a truth assignment f U gt 01 such that ful 1 if and only if qul 6 A1 We claim that f is a truth assignment that makes one or two but not all three literals true in each clause Suppose to the contrary and let C j 61 b c be a clause such that fa fb From the definition off qa qb qcg A r 6 01 and from Lemma 1 T If a t b tj 0g A By construction of graph G NlTj J Nltj aJU Nltj bJU Nltj T U qa qb qc which is contrary to V A being a global defensive alliance

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com