Recent Progress in the Boolean Domain by Bernd Steinbach

By Bernd Steinbach

In latest international, everyone is utilizing a growing number of electronic platforms in everyday life. Such platforms make the most of the elementariness of Boolean values. A Boolean variable can hold in simple terms assorted Boolean values: fake or precise (0 or 1), and has the simplest interference resistance in technical platforms. although, a Boolean functionality exponentially will depend on the variety of its variables. This exponential complexity is the reason for significant difficulties within the means of layout and attention of circuits. in keeping with Moore's legislations, the complexity of electronic platforms nearly doubles each 18 month. This calls for finished wisdom and strategies to resolve very complicated Boolean difficulties. This booklet summarizes the new development within the Boolean area in fixing such matters. half 1 describes the main robust techniques in fixing particularly advanced Boolean difficulties. it really is proven how an exceptionally infrequent answer should be present in a big seek area of greater than 10195 (this is a few 196 decimal digits) varied colour styles. half 2 describes new study into electronic circuits that discover Boolean services. This half includes the chapters "Design" and "Test", which current ideas to difficulties of strength dissipation, and the checking out of electronic circuits utilizing a unique info constitution, in addition to additional themes. half three contributes to the clinical foundation of destiny circuit applied sciences, investigating the necessity for thoroughly new layout equipment for the atomic point of quantum pcs. This part additionally matters itself with circuit buildings in reversible common sense because the foundation for quantum common sense

Show description

Read Online or Download Recent Progress in the Boolean Domain PDF

Best circuits books

Principles of Digital Design

Designed to supply a radical realizing of design's basic rules with out requiring scholars to memorize loads of almost certainly complicated technological info. DLC: built-in circuits - layout - facts processing.

Simulation Techniques and Solutions for Mixed-Signal Coupling in Integrated Circuits

The target of placing `systems on a chip' has been a tough problem that's only in the near past being met. because the global is `analog', placing platforms on a chip calls for placing analog interfaces at the similar chip as electronic processing features. due to the fact that a few processing capabilities are comprehensive extra successfully in analog circuitry, chips with a large number of analog and electronic circuitry are being designed.

Analog Circuits Cookbook

Ian Hickman's earlier books, ''Analog Electronics'' and ''Practical Radio Frequency Handbook'', have supplied engineers and scholars alike with accomplished primers. within the ''Analog Circuits Cookbook'', Hickman bargains suggestion on points of analogue layout, from direct electronic synthesis to radio frequency measurements, and from optoelectronics to logarithmic amplifiers.

Transistor Circuit Techniques: Discrete and Integrated

Completely revised and up to date, this hugely winning textbook publications scholars during the research and layout of transistor circuits. It covers a variety of circuitry, either linear and switching. Transistor Circuit ideas: Discrete and built-in offers scholars with an outline of basic qualitative circuit operation, by means of an exam of study and layout approach.

Additional resources for Recent Progress in the Boolean Domain

Example text

Tr♦❞✉❝t✐♦♥ ❆♣♣❧✐❝❛t✐♦♥s ♦❢ ❇♦♦❧❡❛♥ ✈❛r✐❛❜❧❡s✱ ❇♦♦❧❡❛♥ ♦♣❡r❛t✐♦♥s✱ ❇♦♦❧❡❛♥ ❢✉♥❝✲ t✐♦♥s✱ ❛♥❞ ❇♦♦❧❡❛♥ ❡q✉❛t✐♦♥s ❛r❡ ♥♦t r❡str✐❝t❡❞ t♦ ❝♦♠♣✉t❡rs✱ ❜✉t ❣r♦✇ ✐♥ ♥❡❛r❧② ❛❧❧ ✜❡❧❞s ♦❢ ♦✉r ❞❛✐❧② ❧✐❢❡✳ ■t ♠❛② ❜❡ t❤❛t t❤❡ ❞✐❣✐t❛❧❧② ❝♦♥✲ tr♦❧❧❡❞ ❛❧❛r♠✲❝❧♦❝❦ ✇❛❦❡s ✉s ✐♥ t❤❡ ♠♦r♥✐♥❣❀ ✇❡ ❧✐st❡♥ t♦ t❤❡ s♦✉♥❞s ♦❢ ❞✐❣✐t❛❧ ❛✉❞✐♦ ❜r♦❛❞❝❛sts ❞✉r✐♥❣ ♦✉r ❜r❡❛❦❢❛st❀ ✇❡ ❜✉② t❤❡ t✐❝❦❡t ❢♦r t❤❡ tr❛✐♥ ♦♥ ❛ t✐❝❦❡t ✈❡♥❞✐♥❣ ♠❛❝❤✐♥❡ ❝♦♥tr♦❧❧❡❞ ❜② ❇♦♦❧❡❛♥ ✈❛❧✉❡s❀ ✇❡ ✉s❡ ♦✉r s♠❛rt ♣❤♦♥❡s t❤❛t tr❛♥s♠✐t ❛❧❧ ✐♥❢♦r♠❛t✐♦♥ ❜② ❇♦♦❧❡❛♥ ✈❛❧✉❡s ❢♦r ❜✉s✐♥❡ss❀ ❧♦♦❦ ❛t t❤❡ ✇r✐st ✇❛t❝❤ ✇❤✐❝❤ ❝♦✉♥ts ❛♥❞ s❤♦✇s t❤❡ t✐♠❡ ❜❛s❡❞ ♦♥ ❇♦♦❧❡❛♥ ❞❛t❛ s♦ t❤❛t ✇❡ ❞♦ ♥♦t ♠✐ss t❤❡ ❡♥❞ ♦❢ ♦✉r ✇♦r❦❀ ✇❡ ❣❡t t❤❡ ❜✐❧❧ ❢♦r s❤♦♣♣✐♥❣ ❢r♦♠ ❛ ♣❛② ♠❛❝❤✐♥❡ ✇❤✐❝❤ ❝❛❧❝✉✲ ❧❛t❡s t❤❡ s✉♠ ♦❢ t❤❡ ♣r✐❝❡s ❛♥❞ ✐♥✐t✐❛t❡s ❛ tr❛♥s♠✐ss✐♦♥ ❜❡t✇❡❡♥ ♦✉r ❜❛♥❦ ❛❝❝♦✉♥t ❛♥❞ t❤❡ ❜❛♥❦ ❛❝❝♦✉♥t ♦❢ t❤❡ s❤♦♣❀ ❛♥❞ ✐♥ t❤❡ ❡✈❡♥✐♥❣ ✇❡ ✇❛t❝❤ ❛ ♠♦✈✐❡ ♦♥ ❚❱ ✇❤✐❝❤ ✐s ❛❧s♦ tr❛♥s♠✐tt❡❞ ❜② ❇♦♦❧❡❛♥ ✈❛❧✉❡s✳ ❍❡♥❝❡✱ ✇✐t❤♦✉t t❤✐♥❦✐♥❣ ❛❜♦✉t t❤❡ ❞❡t❛✐❧s✱ ♦✉r ❞❛✐❧② ❧✐❢❡ ✐s s✉rr♦✉♥❞❡❞ ✇✐t❤ ❛ ❣r♦✇✐♥❣ ♥✉♠❜❡r ♦❢ ❞❡✈✐❝❡s ✇❤✐❝❤ ✉t✐❧✐③❡ ❇♦♦❧❡❛♥ ✈❛❧✉❡s ❛♥❞ ♦♣❡r❛t✐♦♥s✳ ●♦r❞♦♥ ❊✳ ▼♦♦r❡ ♣✉❜❧✐s❤❡❞ ✐♥ ✶✾✻✺ ❛ ♣❛♣❡r ❛❜♦✉t t❤❡ tr❡♥❞ ♦❢ ❝♦♠✲ ♣♦♥❡♥ts ✐♥ ✐♥t❡❣r❛t❡❞ ❝✐r❝✉✐ts ✇❤✐❝❤ ❞♦✉❜❧❡ ❛♣♣r♦①✐♠❛t❡❧② ❡✈❡r② ✶✷ t♦ ✷✹ ♠♦♥t❤s✳ ❚❤✐s ♦❜s❡r✈❛t✐♦♥ ✐s ❦♥♦✇♥ ❛s ▼♦♦r❡✬s ▲❛✇✳ ❖❢ ❝♦✉rs❡✱ t❤❡r❡ ❛r❡ ♠❛♥② ♣❤②s✐❝❛❧ ❧✐♠✐ts ✇❤✐❝❤ t❛❦❡ ❡✛❡❝t ❛❣❛✐♥st t❤✐s ❧❛✇✱ ❜✉t ❞✉❡ t♦ t❤❡ ❝r❡❛t✐✈✐t② ♦❢ s❝✐❡♥t✐sts ❛♥❞ ❡♥❣✐♥❡❡rs t❤✐s ❧❛✇ ✐s ✈❛❧✐❞ ✐♥ ❣❡♥❡r❛❧ ❡✈❡♥ ♥♦✇✳ ❚❤❡ ❡①♣♦♥❡♥t✐❛❧ ✐♥❝r❡❛s❡ ♦❢ t❤❡ ❝♦♥tr♦❧ ❡❧❡♠❡♥ts ✐s ❛ str♦♥❣ ❝❤❛❧❧❡♥❣❡ ❢♦r ❛❧❧ ♣❡♦♣❧❡ ✇♦r❦✐♥❣ ✐♥ ❞✐✛❡r❡♥t ✜❡❧❞s ✐♥✢✉❡♥❝❡❞ ❜② ❇♦♦❧❡❛♥ ✈❛❧✉❡s✳ ❚❤❡ ■♥t❡r♥❛t✐♦♥❛❧ ❲♦r❦s❤♦♣ ♦♥ ❇♦♦❧❡❛♥ Pr♦❜❧❡♠s ✭■❲❙❇P✮ ✐s ❛ s✉✐t✲ ❛❜❧❡ ❡✈❡♥t ✇❤❡r❡ ♣❡♦♣❧❡ ❢r♦♠ ❛❧❧ ♦✈❡r t❤❡ ✇♦r❧❞ ♠❡❡t ❡❛❝❤ ♦t❤❡r t♦ r❡♣♦rt ♥❡✇ r❡s✉❧ts✱ t♦ ❞✐s❝✉ss ❞✐✛❡r❡♥t ❇♦♦❧❡❛♥ ♣r♦❜❧❡♠s✱ ❛♥❞ t♦ ❡①✲ ❝❤❛♥❣❡ ♥❡✇ ✐❞❡❛s✳ ❚❤✐s ❜♦♦❦ ❞♦❝✉♠❡♥ts s❡❧❡❝t❡❞ ❛❝t✐✈✐t✐❡s ❛♥❞ r❡s✉❧ts ♦❢ t❤❡ r❡❝❡♥t ♣r♦❣r❡ss ✐♥ t❤❡ ❇♦♦❧❡❛♥ ❞♦♠❛✐♥✳ ❆❧❧ s❡❝t✐♦♥s ❛r❡ ✇r✐tt❡♥ ❢r♦♠ ❛✉t❤♦rs ✇❤♦ ♣r❡s❡♥t❡❞ t❤❡✐r ♥❡✇ r❡s✉❧ts ❛t t❤❡ ✶✵t❤ ■❲❙❇P ✐♥ ■♥tr♦❞✉❝t✐♦♥ ①①① ❙❡♣t❡♠❜❡r ✷✵✶✷ ✐♥ ❋r❡✐❜❡r❣✱ ●❡r♠❛♥②✳ ❚❤❡ ♠♦st ❣❡♥❡r❛❧ ❝❤❛❧❧❡♥❣❡ ✐♥ t❤❡ ❇♦♦❧❡❛♥ ❉♦♠❛✐♥ ♦r✐❣✐♥❛t❡s ❢r♦♠ t❤❡ ❡①♣♦♥❡♥t✐❛❧ ✐♥❝r❡❛s❡ ♦❢ t❤❡ ❝♦♠♣❧❡①✐t② ♦❢ t❤❡ ❇♦♦❧❡❛♥ s②st❡♠s ❛s st❛t❡❞ ✐♥ ▼♦♦r❡✬s ▲❛✇✳ ❈❤❛♣t❡r ✶ ♦❢ t❤✐s ❜♦♦❦ ❞❡❛❧s ✇✐t❤ t❤✐s ♣r♦❜❧❡♠ ✉s✐♥❣ ❛ ❇♦♦❧❡❛♥ t❛s❦ ♦❢ ❛♥ ✉♥❧✐♠✐t❡❞ ❝♦♠♣❧❡①✐t②✳ ❈❤❛♣t❡r ✷ ❛♣♣❧✐❡s t❤❡ ❢♦✉♥❞ ♠❡t❤♦❞s t♦ ❛ ✜♥✐t❡✱ ❜✉t ✉♥❜❡❧✐❡✈❛❜❧❡ ❝♦♠♣❧❡① ♠✉❧t✐♣❧❡✲✈❛❧✉❡❞ ♣r♦❜❧❡♠ ♦❢ ♠♦r❡ t❤❛♥ 10195 ❝♦❧♦r ♣❛tt❡r♥s✳ ❚❤❡ ❧❛st ♦♣❡♥ ♣r♦❜❧❡♠ ✐♥ t❤✐s ✜❡❧❞ ✇❛s r❡❝❡♥t❧② s♦❧✈❡❞✱ t♦♦✳ ❋♦r ❝♦♠♣❧❡t❡♥❡ss✱ t❤❡s❡ r❡s✉❧ts ❛r❡ ❛❞❞❡❞ ❛s ❙❡❝t✐♦♥ ✷✳✺ t♦ t❤✐s ❜♦♦❦✳ ❇❛s✐❝ ✈❡rs✐♦♥s ♦❢ ❛❧❧ ♦t❤❡r s❡❝t✐♦♥s ♦❢ t❤✐s ❜♦♦❦ ❛r❡ ♣✉❜❧✐s❤❡❞ ✐♥ t❤❡ ♣r♦❝❡❡❞✐♥❣s ♦❢ t❤❡ ✶✵t❤ ■❲❙❇P ❬✷✽✼❪✳ ❙✉❝❝❡ss ✐♥ s♦❧✈✐♥❣ s♣❡❝✐❛❧ t❛s❦s ❢♦r ❛♣♣❧✐❝❛t✐♦♥s r❡q✉✐r❡s ❛ ✇❡❧❧ ❞❡✲ ✈❡❧♦♣❡❞ t❤❡♦r❡t✐❝❛❧ ❜❛s✐s✳ ❈❤❛♣t❡r ✸ ♦❢ t❤❡ ❜♦♦❦ ❝♦♥t❛✐♥s ✐♥t❡r❡st✐♥❣ ♥❡✇ r❡s✉❧ts ✇❤✐❝❤ ❝❛♥ ❜❡ ✉t✐❧✐③❡❞ ✐♥ ❢✉t✉r❡ ❛♣♣❧✐❝❛t✐♦♥s✳ ❚❤❡ ❞❡s✐❣♥ ♦❢ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts ✐s t❤❡ ♠❛✐♥ ✜❡❧❞ ✇❤❡r❡ s♦❧✉t✐♦♥s ♦❢ ❇♦♦❧❡❛♥ ♣r♦❜❧❡♠s r❡s✉❧t ✐♥ r❡❛❧ ❞❡✈✐❝❡s✳ ❙❡✈❡♥ ❞✐✛❡r❡♥t t♦♣✐❝s ♦❢ t❤✐s ✜❡❧❞ ❛r❡ ♣r❡s❡♥t❡❞ ✐♥ ❈❤❛♣t❡r ✹✳ ◆♦t ❛❧❧ ♣r♦❞✉❝❡❞ ❞❡✈✐❝❡s ❛r❡ ❢r❡❡ ♦❢ ❡rr♦rs✱ ❞✉❡ t♦ ❣❡✲ ♦♠❡tr✐❝❛❧ str✉❝t✉r❡s ♦❢ ❛ ❢❡✇ ♥❛♥♦♠❡t❡rs ♦♥ t❤❡ ❝❤✐♣s✳ ❍❡♥❝❡✱ ✐t ✐s ❛ ❜✐❣ ❝❤❛❧❧❡♥❣❡ t♦ t❡st s✉❝❤ ❝✐r❝✉✐ts ✇❤✐❝❤ ❝♦♥s✐st ♦❢ ♠✐❧❧✐♦♥s ♦❢ tr❛♥s✐s✲ t♦rs ❛s s✇✐t❝❤✐♥❣ ❡❧❡♠❡♥ts ✐♥ ❧♦❣✐❝ ❣❛t❡s✳ ❈❤❛♣t❡r ✺ ❞❡❛❧s ✇✐t❤ t❤❡s❡ ❇♦♦❧❡❛♥ ♣r♦❜❧❡♠s✳ ❋♦❧❧♦✇✐♥❣ ▼♦♦r❡✬s ▲❛✇✱ ✐♥ t❤❡ ♥❡❛r ❢✉t✉r❡ s✐♥❣❧❡ ❛t♦♠s ♠✉st ❜❡ ✉s❡❞ ❛s ❧♦❣✐❝ ❣❛t❡s✳ ❚❤✐s ✈❡r② str♦♥❣ ❝❤❛♥❣❡ ♦❢ t❤❡ ❜❛s✐❝ ♣❛r❛❞✐❣♠ ❢r♦♠ ❝❧❛ss✐❝❛❧ ❧♦❣✐❝ ❣❛t❡s t♦ r❡✈❡rs✐❜❧❡ q✉❛♥t✉♠ ❣❛t❡s r❡q✉✐r❡s ❝♦♠♣r❡❤❡♥s✐✈❡ ♣r❡♣❛r❛t♦r② ✇♦r❦ ♦❢ s❝✐❡♥t✐sts ❛♥❞ ❡♥❣✐♥❡❡rs✳ ❚❤❡ ✜♥❛❧ ❝❤❛♣t❡r✱ ❈❤❛♣t❡r ✻ ♦❢ t❤✐s ❜♦♦❦ s❤♦✇s r❡❝❡♥t r❡s✉❧ts ✐♥ r❡✲ ✈❡rs✐❜❧❡ ❛♥❞ q✉❛♥t✉♠ ❝♦♠♣✉t✐♥❣✳ ❆ ♠♦r❡ ❞❡t❛✐❧❡❞ ♦✈❡r✈✐❡✇ ♦❢ t❤❡ ❝♦♥t❡♥t ♦❢ t❤✐s ❜♦♦❦ ✐s ❣✐✈❡♥ ✐♥ t❤❡ ❡①❝❡❧❧❡♥t ♣r❡❢❛❝❡ ❜② Pr♦❢✳ ▼✐❧❧❡r✳ ❍❡♥❝❡✱ ✐t r❡♠❛✐♥s t♦ ✇✐s❤ t❤❡ r❡❛❞❡rs ✐♥ t❤❡ ♥❛♠❡ ♦❢ ❛❧❧ ❛✉t❤♦rs ♣❧❡❛s✉r❡ ✇❤✐❧❡ r❡❛❞✐♥❣ t❤✐s ❜♦♦❦ ❛♥❞ ♠❛♥② ♥❡✇ ✐♥s✐❣❤ts ✇❤✐❝❤ ❛r❡ ❤❡❧♣❢✉❧ t♦ s♦❧✈❡ ♠❛♥② ❢✉t✉r❡ t❛s❦s✳ ❇❡r♥❞ ❙t❡✐♥❜❛❝❤ ❉❡♣❛rt♠❡♥t ♦❢ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❚❡❝❤♥✐s❝❤❡ ❯♥✐✈❡rs✐tät ❇❡r❣❛❦❛❞❡♠✐❡ ❋r❡✐❜❡r❣ ❋r❡✐❜❡r❣✱ ❙❛①♦♥②✱ ●❡r♠❛♥② ❊①❝❡♣t✐♦♥❛❧❧② ❈♦♠♣❧❡① ❇♦♦❧❡❛♥ Pr♦❜❧❡♠s ✶✳ ❇♦♦❧❡❛♥ ❘❡❝t❛♥❣❧❡ Pr♦❜❧❡♠ ✶✳✶✳ ❚❤❡ Pr♦❜❧❡♠ t♦ ❙♦❧✈❡ ❛♥❞ ■ts Pr♦♣❡rt✐❡s ❇❡r♥❞ ❙t❡✐♥❜❛❝❤ ❈❤r✐st✐❛♥ P♦st❤♦❢❢ ✶✳✶✳✶✳ ▼♦t✐✈❛t✐♦♥ ❛♥❞ ❙❡❧❡❝t✐♦♥ ♦❢ t❤❡ Pr♦❜❧❡♠ ❚❤❡ ✐♥✢✉❡♥❝❡ ♦❢ t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛ ✐♥ ❛❧♠♦st ❛❧❧ ✜❡❧❞s ♦❢ ♦✉r ❧✐❢❡ ✐s ❣r♦✇✐♥❣✳ ❊✈❡♥ ✐❢ ✇❡ ❡♥❥♦② ♠♦✈✐❡s ✐♥ ❤✐❣❤ q✉❛❧✐t② ♦♥ t❤❡ ❚❱ ♦r tr❛✈❡❧ ❜② ❝❛r t♦ ♦✉r ❢r✐❡♥❞s✱ ✇❡ ❛r❡ str♦♥❣❧② s✉♣♣♦rt❡❞ ❜② t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛✳ ❲❤❡r❡ ✐s t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛ ❤✐❞❞❡♥ ✇❤❡♥ ✇❡ ❛r❡ ✇❛t❝❤✐♥❣ ♠♦✈✐❡s❄ ❚❤❡ ❡①❝❡❧❧❡♥t q✉❛❧✐t② ♦❢ ❍✐❣❤ ❉❡✜♥✐t✐♦♥ ❚❱ ✭❍❉❚❱✮ ✐s ❛❝❤✐❡✈❡❞ ❜❡✲ ❝❛✉s❡ ❜♦t❤ t❤❡ ❝♦❧♦r ✐♥❢♦r♠❛t✐♦♥ ♦❢ ❡❛❝❤ ♣✐①❡❧ ♦❢ t❤❡ s❡q✉❡♥❝❡ ♦❢ ♣✐❝✲ t✉r❡s ❛♥❞ t✇♦ ♦r ♠♦r❡ ❝❤❛♥♥❡❧s ♦❢ s♦✉♥❞ ✐♥❢♦r♠❛t✐♦♥ ❛r❡ tr❛♥s♠✐tt❡❞ ❜② ❛ ❜✐t str❡❛♠ t❤❛t ❝♦♥t❛✐♥s ♦♥❧② t❤❡ ✈❛❧✉❡s ✵ ❛♥❞ ✶✳ ❚❤❡ r❡str✐❝✲ t✐♦♥ t♦ t❤✐s s✐♠♣❧❡st ♦❢ ❛❧♣❤❛❜❡ts r❡str✐❝ts t❤❡ ✐♥✢✉❡♥❝❡ ♦❢ ♥♦✐s❡✱ ❛♥❞ ♣♦ss✐❜❧❡ tr❛♥s♠✐ss✐♦♥ ❡rr♦rs ♦❢ ♦♥❡ ♦r ❛ ❢❡✇ ❜✐ts ✐♥ ❛ ❝❡rt❛✐♥ ♣❡r✐♦❞ ❛r❡ r❡♠♦✈❡❞ ✉s✐♥❣ ❡rr♦r ❝♦rr❡❝t✐♦♥ ❝♦❞❡s✳ ❚❤❡ ♥✉♠❜❡r ♦❢ ❜✐ts ✇❤✐❝❤ ♠✉st ❜❡ tr❛♥s♠✐tt❡❞ ✐♥ ❡❛❝❤ s❡❝♦♥❞ ✐s ❛♣♣r♦①✐♠❛t❡❧② ❡q✉❛❧ t♦ ✷✵ ♠✐❧✲ ❧✐♦♥✳ ❍❡♥❝❡✱ ✇❡ s❡❡ ♦✉r ♠♦❞❡r♥ ❚❱ ❞❡✈✐❝❡ ✐s ✐♥ ❢❛❝t ❛ s♣❡❝✐❛❧✐③❡❞ ❤✐❣❤✲♣❡r❢♦r♠❛♥❝❡ ❝♦♠♣✉t❡r✳ ▲♦♦❦✐♥❣ t♦ t❤❡ s❡❝♦♥❞ ❡①❛♠♣❧❡✿ ✇❡ t②♣✐❝❛❧❧② ❞♦ ♥♦t t❤✐♥❦ ❛❜♦✉t t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛❀ ✇❡ s✐♠♣❧② ✇❛♥t t♦ ✉s❡ t❤❡ ❝❛r t♦ tr❛✈❡❧ ❢r♦♠ ♣❧❛❝❡ ❆ t♦ ❇✳ ■t ✐s ❛ ♣r❡❝♦♥❞✐t✐♦♥ ❢♦r ♦✉r tr❛✈❡❧ t❤❛t t❤❡ ❝❛r ✐s ❧♦❝❛t❡❞ ❛t ❇♦♦❧❡❛♥ ❘❡❝t❛♥❣❧❡ Pr♦❜❧❡♠ ✹ ♣❧❛❝❡ ❆ ❛♥❞ ♥♦t t❛❦❡♥ ❛✇❛② ❜② ❛♥ ✉♥❢r✐❡♥❞❧② ♣❡rs♦♥✳ ❆♥ ❡❧❡❝tr♦♥✐❝ ✐♠♠♦❜✐❧✐③❡r s②st❡♠ ❜❛s❡❞ ♦♥ ❛ str♦♥❣❧② ❡♥❝♦❞❡❞ ❜✐♥❛r② ❦❡② ❤❡❧♣s t♦ s❛t✐s❢② t❤✐s ♣r❡❝♦♥❞✐t✐♦♥✳ ◆❡①t✱ ✇❡ ❤❛✈❡ t♦ st❛rt ❛♥❞ ♥♦t t♦ ❦✐❧❧ t❤❡ ❡♥❣✐♥❡✳ ❚❤✐s ✐s s✉♣♣♦rt❡❞ ❜② t❤❡ ❡♥❣✐♥❡ ♠❛♥❛❣❡♠❡♥t s②st❡♠✱ ✇❤✐❝❤ ❝❛❧❝✉❧❛t❡s ✐♥ r❡❛❧ t✐♠❡ t❤❡ ❜✐♥❛r② ✐♥❢♦r♠❛t✐♦♥ ❢r♦♠ ♠❛♥② s❡♥s♦rs ❛♥❞ ❝♦♥tr♦❧s t❤❡ ♥❡❡❞❡❞ ❛♠♦✉♥t ♦❢ ❣❛s ❛♥❞ t❤❡ ❝♦rr❡❝t tr✐❣❣❡r ♠♦♠❡♥t ❢♦r ❡❛❝❤ ❝②❧✐♥❞❡r ♦❢ t❤❡ ❡♥❣✐♥❡✳ ❍❡r❡ t❤❡ ♥❡①t ✐♠♣♦rt❛♥t ❝♦♠♣✉t❡r ✇♦r❦s ✐♥ ♦✉r ❝❛r✳ ❙t♦♣♣✐♥❣ t❤❡ ❝❛r ❜❡❢♦r❡ r❡❛❝❤✐♥❣ ❛♥ ♦❜st❛❝❧❡ ✐s ❛s ✐♠♣♦rt❛♥t ❛s ❞r✐✈✐♥❣ t❤❡ ❝❛r✳ ❚❤❡ ❛♥t✐✲❧♦❝❦ ❜r❛❦✐♥❣ s②st❡♠ ✭❆❇❙✮ ❤❡❧♣s t❤❡ ❞r✐✈❡r ✐♥ ❝r✐t✐❝❛❧ s✐t✉❛t✐♦♥s ❜② ❡✈❛❧✉❛t✐♦♥ ♦❢ t❤❡ ✐♥❢♦r♠❛t✐♦♥ ❢r♦♠ r♦t❛t✐♦♥ s❡♥s♦rs ♦❢ t❤❡ ✇❤❡❡❧s ❛♥❞ s❡♣❛r❛t❡ ❝♦♥tr♦❧ ♦❢ ❛❧❧ ❢♦✉r ❜r❡❛❦s✳ ❚❤❡s❡ ❛r❡ ♦♥❧② s♦♠❡ s❡❧❡❝t❡❞ t❛s❦s ✇❤❡r❡ t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛ ✐♥s✐❞❡ ❝♦♠♣✉t❡rs s✉♣♣♦rts t❤❡ ❞r✐✈❡r ♦❢ ❛ ❝❛r✳ ❋✉rt❤❡r ❡①❛♠♣❧❡s ❛r❡ ❡❧❡❝tr♦♥✐❝ ❜r❛❦❡✲❢♦r❝❡ ❞✐str✐❜✉t✐♦♥ ✭❊❇❉✮✱ ❡❧❡❝tr♦♥✐❝ st❛❜✐❧✐t② ❝♦♥tr♦❧ ✭❊❙❈✮✱ ♦r ●P❙ ♥❛✈✐❣❛t✐♦♥ s②st❡♠s✳ ❚❤❡ r❡q✉✐r❡❞ ❤✐❣❤ s❡❝✉r✐t② ✐s r❡❛❝❤❡❞ ✐♥ ❛❧❧ t❤❡s❡ s②st❡♠s ❜② t❤❡ ✉t✐❧✐③❛t✐♦♥ ♦❢ ❜✐♥❛r② ✈❛❧✉❡s✱ ✇❤✐❝❤ ❤❛✈❡ t❤❡ ❤✐❣❤❡st ♣♦ss✐❜❧❡ ♥♦✐s❡ ✐♠♠✉♥✐t②✳ ❚❤❡ ❜❡♥❡✜t ♦❢ ❇♦♦❧❡❛♥ ❝❛❧❝✉❧❛t✐♦♥s ✇❛s ❞✐s❝♦✈❡r❡❞ ❜② ❑♦♥r❛❞ ❩✉s❡ ❬✸✹✾❪✳ ■♥ ✶✾✸✽✱ ❤❡ ✜♥✐s❤❡❞ ❤✐s ✜rst ❝♦♠♣✉t❡r ❩✶✳ ❚❤✐s ❡✈❡♥t ♠❛r❦❡❞ t❤❡ st❛rt✐♥❣ ♣♦✐♥t ♦❢ ❛ ❣✐❣❛♥t✐❝ ❞❡✈❡❧♦♣♠❡♥t ✐♥ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ✐ts ❛♣♣❧✐❝❛t✐♦♥s✳ ❇❛s❡❞ ♦♥ t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛✱ ❑♦♥r❛❞ ❩✉s❡ ❛♥❞ ♠❛♥② ♦t❤❡r ❡♥❣✐♥❡❡rs str♦♥❣❧② ✐♠♣r♦✈❡❞ t❤❡ t❡❝❤♥♦❧♦❣② ♦❢ ❝♦♠♣✉t❡rs ❛♥❞ ♦t❤❡r ❝♦♥tr♦❧ s②st❡♠s✳ ❇❛s❡❞ ♦♥ t❤❡ s✉❝❝❡ss ♦❢ t❤❡ ❞❡✈❡❧♦♣♠❡♥t ♦❢ ❞✐❣✐t❛❧ ✐♥t❡❣r❛t❡❞ ❝✐r❝✉✐ts✱ ●♦r❞♦♥ ❊✳ ▼♦♦r❡ ♣✉❜❧✐s❤❡❞ ✐♥ ✶✾✻✺ ❛♥ ❛rt✐❝❧❡ t❤❛t ✐♥❝❧✉❞❡❞ t❤❡ ♣r❡✲ ❞✐❝t✐♦♥ ♦❢ ❛♥ ❡①♣♦♥❡♥t✐❛❧ ✐♥❝r❡❛s❡ ♦❢ t❤❡ ♥✉♠❜❡r ♦❢ ❝♦♠♣♦♥❡♥ts ✐♥ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts ✐♥ ✜①❡❞ ♣❡r✐♦❞s ♦❢ t✐♠❡✳ ❚❤❛t ♠❡❛♥s t❤❡ ♣❡r❢♦r♠❛♥❝❡ ♦❢ ❡❧❡❝tr♦♥✐❝ ❞❡✈✐❝❡s ❞♦✉❜❧❡s ❛♣♣r♦①✐♠❛t❡❧② ❡✈❡r② ♦♥❡ t♦ t✇♦ ②❡❛rs✳ ❊✈❛❧✉❛t✐♥❣ t❤❡ r❡❛❝❤❡❞ ♥✉♠❜❡r ♦❢ tr❛♥s✐st♦rs ♦❢ ✐♥t❡❣r❛t❡❞ ❝✐r❝✉✐ts✱ t❤❡ tr✉t❤ ♦❢ t❤❡ s♦✲❝❛❧❧❡❞ ▼♦♦r❡✬s ▲❛✇ ❝❛♥ ❜❡ ❛❝❝❡♣t❡❞ ✉♥t✐❧ ♥♦✇✳ ❚❤✐s ❡①♣♦♥❡♥t✐❛❧ ✐♥❝r❡❛s❡ ♦❢ t❤❡ ♥✉♠❜❡r ♦❢ ❝♦♠♣♦♥❡♥ts ✐♥ ❡❧❡❝tr♦♥✐❝ ❞❡✈✐❝❡s ♠❛♣s ❞✐r❡❝t❧② ♦♥t♦ t❤❡ ❝♦♠♣❧❡①✐t② ♦❢ t❤❡ r❡❛❧✐③❡❞ ❇♦♦❧❡❛♥ ❢✉♥❝t✐♦♥s ❛♥❞ ❣❡♥❡r❛t❡s str♦♥❣ ❝❤❛❧❧❡♥❣❡s ❢♦r t❤❡✐r r❡♣r❡s❡♥t❛t✐♦♥ ❛♥❞ ♠❛♥✐♣✉❧❛t✐♦♥✳ ▼❛♥② ❞✐✛❡r❡♥t ❇♦♦❧❡❛♥ t❛s❦s ♠✉st ❜❡ s♦❧✈❡❞ ❞✐r❡❝t❧② ❢♦r t❤❡ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts✳ ❚❤❡s❡ t❛s❦s ❝♦♠♣r✐s❡ t❤❡ ❞❡s✐❣♥✱ ❛♥❛❧②s✐s✱ ❝♦♠♣❛r✐s♦♥ ❛♥❞ t❤❡ t❡st ♦❢ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts✳ ❇♦t❤ t❤❡ ❛✈❛✐❧❛❜❧❡ ❧❛r❣❡r ♠❡♠♦r② s✐③❡ ❛♥❞ t❤❡ ✈❡r② ❤✐❣❤ ❝♦♠♣✉t❛t✐♦♥ ♣♦✇❡r ♦❢ s❡✈❡r❛❧ ❝♦♠✲ ❚❤❡ Pr♦❜❧❡♠ t♦ ❙♦❧✈❡ ❛♥❞ ■ts Pr♦♣❡rt✐❡s ♣✉t❛t✐♦♥ ❝♦r❡s ♦❢ t❤❡ ✺ ❝❡♥tr❛❧ ♣r♦❝❡ss✐♥❣ ✉♥✐t ✭❈P❯✮ ♦r ❡✈❡♥ s❡✈❡r❛❧ ❣r❛♣❤✐❝s ♣r♦❝❡ss✐♥❣ ✉♥✐t ✭●P❯✮ ♠❛❦❡ t❤❡ r❡✲ ❤✉♥❞r❡❞s ♦❢ ❝♦r❡s ♦❢ t❤❡ ❛❧✐③❛t✐♦♥ ♦❢ ❛♣♣❧✐❝❛t✐♦♥s ♦❢ ❛❧❧ ✜❡❧❞s ♦❢ ♦✉r ❧✐❢❡ ♣♦ss✐❜❧❡✳ ❆❧t♦❣❡t❤❡r✱ t❤✐s ♦r✐❣✐♥❛t❡s ✐♥ ❛ ✇✐❞❡ r❛♥❣❡ ♦❢ ❞✐✛❡r❡♥t ❇♦♦❧❡❛♥ t❛s❦s✳ ■t ✐s ❛ ❝♦♠✲ ♠♦♥ ♣r♦♣❡rt② ♦❢ t❤❡s❡ t❛s❦s t❤❛t t❤❡ ♥✉♠❜❡r ♦❢ ✉s❡❞ ❇♦♦❧❡❛♥ ✈❛r✐✲ ❛❜❧❡s ❛♥❞ ❝♦♥s❡q✉❡♥t❧② t❤❡ s✐③❡ ♦❢ t❤❡ ❇♦♦❧❡❛♥ ❢✉♥❝t✐♦♥ ❣r♦✇s ♠♦r❡ ❛♥❞ ♠♦r❡ ✐♥t♦ ❡①tr❡♠❡ r❡❣✐♦♥s✳ ■t ✐s ♥♦t ♣♦ss✐❜❧❡ t♦ ❞✐s❝✉ss ❛❧❧ t❤❡s❡ ❇♦♦❧❡❛♥ ♣r♦❜❧❡♠s ✐♥ t❤✐s ❜♦♦❦✳ ❍♦✇❡✈❡r✱ ✇❡ ✇❛♥t t♦ ❝♦♥tr✐❜✉t❡ ✐♥ ❛ ❣❡♥❡r❛❧✐③❡❞ ♠❛♥♥❡r t♦ t❤❡ ❝♦♠✲ ♣❧❡①✐t② ♣r♦❜❧❡♠ ✐♥ t❤❡ ❇♦♦❧❡❛♥ ❞♦♠❛✐♥✳ ■♥ ♦r❞❡r t♦ ❞♦ t❤❛t ✇❡ s❡❧❡❝t ❛ ❇♦♦❧❡❛♥ t❛s❦ ✇❤✐❝❤✿ ✶✳ ✐s ❡❛s② t♦ ✉♥❞❡rst❛♥❞✱ ✷✳ r❡q✉✐r❡s ♠❛♥② ❇♦♦❧❡❛♥ ❝❛❧❝✉❧❛t✐♦♥s✱ ✸✳ ❞♦❡s ♥♦t ❤❛✈❡ ❛♥② r❡str✐❝t✐♦♥ ✐♥ t❤❡ s✐③❡✱ ❛♥❞ ✹✳ ❤❛s ❛ s✐♠♣❧❡ s♦❧✉t✐♦♥ ❢♦r ❡❛❝❤ ✜①❡❞ s✐③❡ ♦❢ t❤❡ ♣r♦❜❧❡♠✳ ❙❧✐❣❤t❧② ✐♥❝r❡❛s❡❞ ✈❛❧✉❡s ♦❢ t❤❡ ❝♦♥tr♦❧ ♣❛r❛♠❡t❡rs ♦❢ s✉❝❤ ❛ ♣r♦❜❧❡♠ ❝❛♥ ❝❛✉s❡ ❛♥ ❡①t❡♥s✐♦♥ ♦❢ t❤❡ r❡q✉✐r❡❞ r✉♥t✐♠❡ ❢♦r t❤❡ s♦❧✉t✐♦♥ ♣r♦❝❡ss ♦❢ s❡✈❡r❛❧ ♦r❞❡rs ♦❢ ♠❛❣♥✐t✉❞❡✳ ❋✐♥❞✐♥❣ ✐♠♣r♦✈❡♠❡♥ts ❢♦r t❤❡ s♦❧✉t✐♦♥ ♣r♦❝❡ss ❢♦r s✉❝❤ ❛ t❛s❦ ❝❛♥ ❜❡ ✉s❡❢✉❧ ❢♦r ♦t❤❡r ❇♦♦❧❡❛♥ t❛s❦s✳ ❆ t❛s❦ ✇❤✐❝❤ ❤♦❧❞s t❤❡ ❡♥✉♠❡r❛t❡❞ r❡q✉✐r❡♠❡♥ts ✐s t❤❡ ❝❛❧❝✉❧❛t✐♦♥ ♦❢ t❤❡ ♠❛①✐♠❛❧ ♥✉♠❜❡r ♦❢ ❡❞❣❡s ✇✐t❤✐♥ ❛ ❜✐♣❛rt✐t❡ ❣r❛♣❤ t❤❛t ❞♦❡s ♥♦t ❝♦♥t❛✐♥ ❛♥② ❝②❝❧❡s ♦❢ t❤❡ ❧❡♥❣t❤ ❢♦✉r✳ ❚❤✐s ♣r♦❜❧❡♠ ♦❢ ❣r❛♣❤ t❤❡♦r② ✐s ❡q✉✐✈❛❧❡♥t t♦ r❡❝t❛♥❣❧❡✲❢r❡❡ ❣r✐❞s✳ ❲❡ ❡①♣❧❛✐♥ t❤❡s❡ t✇♦ ❞✐✛❡r❡♥t ✈✐❡✇s ♦❢ t❤❡ s❡❧❡❝t❡❞ ❇♦♦❧❡❛♥ t❛s❦ ✐♥ t❤❡ ♥❡①t t✇♦ s✉❜s❡❝t✐♦♥s✳ ✶✳✶✳✷✳ ❚❤❡ Pr♦❜❧❡♠ ✐♥ ❈♦♥t❡①t ♦❢ ●r❛♣❤ ❚❤❡♦r② ●r❛♣❤s ❛♣♣❡❛r ✐♥ ♦✉r ❧✐❢❡ ✇✐t❤♦✉t t❤✐♥❦✐♥❣ ❛❜♦✉t t❤❡♠✱ ❧✐❦❡ t❤❡ ❇♦♦❧❡❛♥ ❆❧❣❡❜r❛ ❞✐s❝✉ss❡❞ ✐♥ t❤❡ ♣r❡✈✐♦✉s s✉❜s❡❝t✐♦♥✳ ❣r❛♣❤ vi ∈ V G ❇❛s✐❝❛❧❧②✱ ❛ ✐s s♣❡❝✐✜❡❞ ❜② t✇♦ s❡ts✳ ❚❤❡ ✜rst s❡t ❝♦♥t❛✐♥s t❤❡ ✈❡rt✐❝❡s ♦❢ t❤❡ ❣r❛♣❤✳ ❆♥ ❡①❛♠♣❧❡ ♦❢ t❤❡ ❡❧❡♠❡♥ts ♦❢ t❤✐s s❡t ❛r❡ t❤❡ ❇♦♦❧❡❛♥ ❘❡❝t❛♥❣❧❡ Pr♦❜❧❡♠ ✻ ❝r♦ss✐♥❣s ✐♥ ❛ ❝✐t②✳ ❚❤❡ s❡❝♦♥❞ s❡t ❝♦♥t❛✐♥s t❤❡ ❡❞❣❡s ej ∈ E ✳ ❈♦♠✲ ♣❧❡t✐♥❣ ♦✉r ❡①❛♠♣❧❡✱ t❤❡ r♦❛❞s ✇❤✐❝❤ ❝♦♥♥❡❝t t❤❡ ❝r♦ss✐♥❣s✱ ❛r❡ t❤❡ ❡❧❡♠❡♥ts ♦❢ t❤✐s s❡❝♦♥❞ s❡t ❢♦r t❤❡ ❡①❛♠♣❧❡ ♦❢ t❤❡ r♦❛❞ ♥❡t✇♦r❦ ♦❢ ❛ ❝✐t②✳ ❆ ❣r❛♣❤ ❝❛♥ ❜❡ ❜✉✐❧t ✐♥ ❛ s✐♠✐❧❛r ✇❛② ❢♦r t❤❡ r❛✐❧ ♥❡t✇♦r❦ ♦❢ ❛ r❛✐❧✇❛② st❛t✐♦♥✳ ❚❤❡ ✈❡rt✐❝❡s ❛r❡ ✐♥ t❤✐s ❝❛s❡ t❤❡ s✇✐t❝❤❡s✱ ❛♥❞ t❤❡ ❡❞❣❡s ❛r❡ t❤❡ r❛✐❧s ❜❡t✇❡❡♥ t❤❡♠✳ ❋r♦♠ ❛ ♠♦r❡ ❣❡♥❡r❛❧ ♣♦✐♥t ♦❢ ✈✐❡✇✱ t❤❡ ❣r❛♣❤ ❝❛♥ ❜❡ ❜✉✐❧t ❢♦r ❛ r❛✐❧ ♥❡t✇♦r❦ ♦❢ ❛ ✇❤♦❧❡ ❝♦✉♥tr② ♦r ❡✈❡♥ ❛ ❝♦♥t✐♥❡♥t ✇❤❡r❡ t❤❡ ✈❡rt✐❝❡s ❛r❡ ✐♥ t❤✐s ❝❛s❡ t❤❡ ❝✐t✐❡s ❝♦♥♥❡❝t❡❞ t♦ t❤❡ r❛✐❧ ♥❡t✇♦r❦✱ ❛♥❞ t❤❡ ❡❞❣❡s ❛r❡ t❤❡ r❛✐❧s ❜❡t✇❡❡♥ t❤❡s❡ ❝✐t✐❡s✳ ❚❤❡ s❡ts ♦❢ t❤❡ ❣r❛♣❤ ♠✉st ♥♦t ♥❡❝❡ss❛r✐❧② ❜❡ t❤❡ r❡♣r❡s❡♥t❛t✐♦♥ ♦❢ r❡❛❧ t❤✐♥❣s ❧✐❦❡ str❡❡ts ♦r r❛✐❧s✳ ■♥ t❤❡ ❝❛s❡ ♦❢ ❛ ✢✐❣❤t ♥❡t✇♦r❦ ♦❢ ❛♥ ❛✐r ❝♦♠♣❛♥②✱ t❤❡ ♣r♦✈✐❞❡❞ ✢✐❣❤t ❝♦♥♥❡❝t✐♦♥s ❜❡t✇❡❡♥ s❡❧❡❝t❡❞ ❛✐r♣♦rts ❞❡s❝r✐❜❡ t❤❡ ❡❞❣❡s ♦❢ ✈❡rt✐❝❡s V E ❛♥❞ ❜✉✐❧❞ t♦❣❡t❤❡r ✇✐t❤ t❤❡s❡ ❛✐r♣♦rts ❛s ❛ s❡t t❤❡ ❣r❛♣❤ G(V, E)✳ ●r❛♣❤s ❝❛♥ ❜❡ s♣❧✐t ✐♥t♦ ❞✐r❡❝t❡❞ ❛♥❞ ✉♥❞✐r❡❝t❡❞ ❣r❛♣❤s✱ ❜❛s❡❞ ♦♥ t❤❡ ❞✐r❡❝t✐♦♥ ♦❢ t❤❡ ❡❞❣❡s✳ ❲❡ ✇✐❧❧ ❢♦❝✉s ♦♥ ✉♥❞✐r❡❝t❡❞ ❣r❛♣❤s✳ ❋✉rt❤❡r✲ ♠♦r❡✱ ✐t ✐s ♣♦ss✐❜❧❡ t♦ ❞✐st✐♥❣✉✐s❤ ❣r❛♣❤s ❜❛s❡❞ ♦♥ ✇❡✐❣❤ts ❛ss♦❝✐❛t❡❞ t♦ t❤❡ ✈❡rt✐❝❡s ❛♥❞ ✴ ♦r t♦ t❤❡ ❡❞❣❡s✳ ❲❡ ❝♦♥❝❡♥tr❛t❡ ✐♥ t❤✐s s❡❝t✐♦♥ ♦♥ ✉♥✇❡✐❣❤t❡❞ ❣r❛♣❤s✳ ❖♥❡ ♠♦r❡ ♣♦ss✐❜✐❧✐t② ❞✐✈✐❞✐♥❣ ❣r❛♣❤s ✐♥ ❝❡rt❛✐♥ ❝❧❛ss❡s ✐s t❤❡ s♣❧✐t ♦❢ t❤❡ s❡t ♦❢ ✈❡rt✐❝❡s ✐♥t♦ s✉❜s❡ts ❛♥❞ t❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ ❝♦♥str❛✐♥ts ❢♦r t❤❡ ❡❞❣❡s ❜❡t✇❡❡♥ t❤❡s❡ s✉❜s❡ts✳ ❚❤❡ ♣r♦❜❧❡♠ ✇❡ ✇❛♥t t♦ st✉❞② ✐♥ t❤✐s s❡❝t✐♦♥ ✐s ❞❡✜♥❡❞ ❜② s♦✲❝❛❧❧❡❞ ❜✐♣❛rt✐t❡ ❣r❛♣❤s ✳ V1 ❛♥❞ V2 ✇✐t❤ ♦❢ ❛ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ❝♦♥♥❡❝ts ♦♥❡ ✈❡rt❡① vj ∈ V2 ✳ V ✐s ❞✐✈✐❞❡❞ V = V1 ∪ V2 ✳ ❊❛❝❤ ❡❞❣❡ vi ∈ V1 ✇✐t❤ ♦♥❡ ✈❡rt❡① ■♥ ❛ ❜✐♣❛rt✐t❡ ❣r❛♣❤ t❤❡ s❡t ♦❢ ✈❡rt✐❝❡s ✐♥t♦ t✇♦ s✉❜s❡ts ♦❢ ✈❡rt✐❝❡s ❈♦♥s❡q✉❡♥t❧②✱ t❤❡r❡ ❛r❡ ♥♦ ❡❞❣❡s t❤❛t ❝♦♥♥❡❝t t✇♦ ✈❡rt✐❝❡s ♦❢ t❤❡ s✉❜s❡t V1 ♦r t✇♦ ✈❡rt✐❝❡s ♦❢ t❤❡ s✉❜s❡t V2 ✳ ❆ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ❝❛♥ ❜❡ ✉s❡❞ t♦ ❞❡s❝r✐❜❡ ❛ss✐❣♥♠❡♥ts ♦❢ ✐t❡♠s ♦❢ t✇♦ s❡ts✳ ❆s ❡①❛♠♣❧❡✱ ✇❡ ❝❛♥ t❛❦❡ t❤❡ s❡t ♦❢ ❜✉s st❛t✐♦♥s ❛♥❞ t❤❡ s❡t ♦❢ ❜✉s ❧✐♥❡s ✐♥ ❛ ❝✐t②✳ ❆♥ ❡❞❣❡ ♦❢ t❤❡ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ❞❡s❝r✐❜❡s t❤❡ ❛ss✐❣♥♠❡♥t t❤❛t t❤❡ ❜✉s ❧✐♥❡ st♦♣s ❛t t❤❡ ❝♦♥♥❡❝t❡❞ ❜✉s st❛t✐♦♥✳ ❚❤❡ ✇✐❞❡ r❛♥❣❡ ♦❢ ❛♣♣❧✐❝❛t✐♦♥s ♦❢ ❜✐♣❛rt✐t❡ ❣r❛♣❤s ❜❡❝♦♠❡s ✈✐s✐❜❧❡ ❜② ❛ s❡❝♦♥❞ ❡①❛♠♣❧❡✳ ❚❤❡ t✇♦ s❡ts ❛r❡✱ ✐♥ t❤✐s ❡①❛♠♣❧❡✱ t❤❡ ♣r♦❢❡ss♦rs ♦❢ ❛ ✉♥✐✈❡rs✐t② ❛♥❞ t❤❡ ♠♦❞✉❧❡s st✉❞✐❡❞ ❜② t❤❡ st✉❞❡♥ts✳ ■♥ t❤✐s ❝❛s❡✱ ❛r❡❛s ❚❤❡ Pr♦❜❧❡♠ t♦ ❙♦❧✈❡ ❛♥❞ ■ts Pr♦♣❡rt✐❡s ✼ ❢r♦♠ t❤❡ ❡①♣❡r✐❡♥❝❡s ♦❢ t❤❡ ♣r♦❢❡ss♦rs ❞❡❝✐❞❡ ✇❤✐❝❤ ♣♦ss✐❜❧❡ ♠♦❞✉❧❡s t♦ t❡❛❝❤✳ ❙✉❝❤ ❛ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ✐s ❛♥ ✐♠♣♦rt❛♥t ✐♥♣✉t t♦ s♦❧✈❡ t❤❡ ❞✐✣❝✉❧t ♣r♦❜❧❡♠ ♦❢ ❜✉✐❧❞✐♥❣ t❤❡ ❝❧❛ss s❝❤❡❞✉❧❡ ❢♦r ❛ s❡♠❡st❡r✳ ❆ t❤✐r❞ ❡①❛♠♣❧❡ ❜r✐♥❣s ✉s ✜♥❛❧❧② t♦ t❤❡ ♣r♦❜❧❡♠ t♦ s♦❧✈❡✳ ❍❡r❡ ✇❡ t❛❦❡ NAND✲❣❛t❡s ♦❢ ❛ ❝✐r❝✉✐t ❛♥❞ ❛s NAND✲❣❛t❡s✳ ❚❤❡ NAND✲❣❛t❡s ❛r❡ ❛s t❤❡ ✜rst s❡t ♦❢ ✈❡rt✐❝❡s t❤❡ ✐♥♣✉ts ♦❢ ❛ s❡❝♦♥❞ s❡t t❤❡ ♦✉t♣✉ts ♦❢ t❤❡ s❛♠❡ ❝❤♦s❡♥ ❞✉❡ t♦ t❤❡ ♣r♦♣❡rt② t❤❛t ❡❛❝❤ ❇♦♦❧❡❛♥ ❢✉♥❝t✐♦♥ ❝❛♥ ❜❡ ❜✉✐❧t ✇✐t❤ t❤✐s t②♣❡ ♦❢ ❣❛t❡s ❛❧♦♥❡✳ ❊❛❝❤ ❣❛t❡ ♠❡r❣❡s t❤❡ ❧♦❣✐❝❛❧ ✈❛❧✉❡s ♦❢ ✐ts ✐♥♣✉ts t♦ t❤❡ ❧♦❣✐❝❛❧ ✈❛❧✉❡ ♦♥ ✐ts ♦✉t♣✉t✳ ❍❡♥❝❡✱ t❤❡ ❣❛t❡s ♦❢ ❛ ❝✐r❝✉✐t ❣❡♥❡r❛t❡ ❛ss✐❣♥♠❡♥ts ♦❢ ❡❞❣❡s ♦❢ t❤❡ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ❞✉❡ t♦ t❤❡ ✐♥t❡r♥❛❧ str✉❝t✉r❡ ♦❢ t❤❡ ❣❛t❡✳ ■♥ ♦r❞❡r t♦ r❡❛❝❤ t❤❡ ♥❡❡❞❡❞ ❜❡❤❛✈✐♦r ♦❢ t❤❡ ❝✐r❝✉✐t✱ t❤❡ ♦✉t♣✉ts ♦❢ ✐♥t❡r♥❛❧ ❣❛t❡s ♠✉st ❜❡ ❝♦♥♥❡❝t❡❞ ❜② ✇✐r❡s ✇✐t❤ ✐♥♣✉ts ❢r♦♠ ❝❡rt❛✐♥ ♦t❤❡r ❣❛t❡s✳ ❚❤❡s❡ ✇✐r❡s ❛❧s♦ ❞❡s❝r✐❜❡ ❛ss✐❣♥♠❡♥ts ❜❡t✇❡❡♥ t❤❡ s✉❜s❡ts ♦❢ ❡❞❣❡s ❛♥❞ ♠✉st ❜❡ ❡①♣r❡ss❡❞ ❜② ❡❞❣❡s ✐♥ t❤❡ ❜✐♣❛rt✐t❡ ❣r❛♣❤✳ ❚❤❡r❡ ❛r❡ t✇♦ t②♣❡s ♦❢ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts✿ ❝♦♠❜✐♥❛t♦r✐❛❧ ❝✐r❝✉✐ts ❛♥❞ s❡q✉❡♥t✐❛❧ ❝✐r❝✉✐ts✳ ❇♦t❤ ♦❢ t❤❡♠ ❝❛♥ ❜❡ r❡❛❧✐③❡❞ ❜② NAND✲❣❛t❡s✳ ❆ ❜✐♣❛rt✐t❡ ❣r❛♣❤✱ ❛s ❡①♣❧❛✐♥❡❞ ✐♥ t❤❡ ❧❛st ♣❛r❛❣r❛♣❤✱ ✐s s✉✐t❛❜❧❡ ❢♦r t❤❡✐r ❞❡s❝r✐♣t✐♦♥✳ ❆ss✉♠❡ t❤❛t ❛ ❝♦♠❜✐♥❛t♦r✐❛❧ ❝✐r❝✉✐t ♠✉st ❜❡ ❞❡s✐❣♥❡❞✳ ❚❤❡ ❛ss♦❝✐❛t❡❞ ❜✐♣❛rt✐t❡ ❣r❛♣❤ ♠✉st ♥♦t ✐♥❝❧✉❞❡ ❛ ❝②❝❧❡ ♦❢ t❤❡ ❧❡♥❣t❤ ✹ ❜❡❝❛✉s❡ s✉❝❤ ❛ ❝②❝❧❡ ❝❛✉s❡s ❛ ♠❡♠♦r② ❜❡❤❛✈✐♦r s♦ t❤❡♥ ✇❡ ❤❛✈❡ ❛ s❡q✉❡♥t✐❛❧ ❝✐r❝✉✐t✳ ❲❡ ❞♦ ♥♦t ✇❛♥t t♦ ❣♦ ❞❡❡♣❡r ✐♥t♦ t❤❡ ❞❡t❛✐❧s ♦❢ ❞✐❣✐t❛❧ ❝✐r❝✉✐ts ✐♥ t❤✐s s❡❝t✐♦♥✱ ❜✉t ✇❡ ❝♦♥❝❡♥tr❛t❡ ♦♥ ❜✐♣❛rt✐t❡ ❣r❛♣❤s ✇❤✐❝❤ ❞♦ ♥♦t ✐♥❝❧✉❞❡ ❛♥② ❝②❝❧❡s ♦❢ t❤❡ ❧❡♥❣t❤ ✹✳ ◆♦✇ ✇❡ ❛r❡ ♣r❡♣❛r❡❞ t♦ ❞❡s❝r✐❜❡ ❢♦r♠❛❧❧② t❤❡ ♣r♦❜❧❡♠ t♦ s♦❧✈❡✳ ❚❤❡ s❡t ♦❢ ✈❡rt✐❝❡s ✈❡rt✐❝❡s V1 V ♦❢ t❤❡ ❜✐♣❛rt✐t❡ V2 ✇✐t❤ ❣r❛♣❤ ✐s ❞✐✈✐❞❡❞ ✐♥t♦ t❤❡ s✉❜s❡ts ♦❢ ❛♥❞ V1 ∪ V2 = V , V1 ∩ V2 = ∅ , m = |V1 | n = |V2 | ✐s t❤❡ ♥✉♠❜❡r ♦❢ ✈❡rt✐❝❡s ✐♥ t❤❡ s✉❜s❡t V1 , ✐s t❤❡ ♥✉♠❜❡r ♦❢ ✈❡rt✐❝❡s ✐♥ t❤❡ s✉❜s❡t V2 .

T❤♦✉t ❧♦ss ♦❢ t❤❡ ♣r♦♣❡rt② t❤❛t ♠❛❦❡s ✐t ❝②❝❧❡✲✹✲❢r❡❡✳ ❆♥ ❡①❤❛✉st✐✈❡ ❡✈❛❧✉❛t✐♦♥ ♦❢ ❛❧❧ ❜✐♣❛rt✐t❡ ❣r❛♣❤s G3,4 (V1 , V2 , E) ❝♦♥✜r♠s t❤❛t maxc4 f (3, 4) = 7✳ ✶✳✶✳✸✳ ❘❡❝t❛♥❣❧❡✲❋r❡❡ ●r✐❞s ❆♥ ❛❧t❡r♥❛t✐✈❡ t♦ t❤❡ ❣r❛♣❤✐❝❛❧ r❡♣r❡s❡♥t❛t✐♦♥ ♦❢ ❛ ❜✐♣❛rt✐t❡ ❣r❛♣❤ Gm,n (V1 , V2 , E) ❛ ❣r✐❞ ✳ ✐s ❛♥ ❛❞❥❛❝❡♥❝② ♠❛tr✐①✳ ❙✉❝❤ ❛ ♠❛tr✐① ✐s ❛❧s♦ ❝❛❧❧❡❞ ❲❡ r❡❢❡r t♦ t❤✐s ❛❜❜r❡✈✐❛t✐♦♥ ✐♥ t❤❡ r❡st ♦❢ ❈❤❛♣t❡r ✶✳ ❚❤❡ s✉❜s❡t V1 ⊂ V ✐s ♠❛♣♣❡❞ t♦ t❤❡ s❡t ♦❢ r♦✇s R ♦❢ t❤❡ ❣r✐❞✿ v1i ∈ V1 =⇒ ri ∈ R . ❙✐♠✐❧❛r❧②✱ ✇❡ ♠❛♣ t❤❡ s✉❜s❡t ❣r✐❞✿ V2 ⊂ V C t♦ t❤❡ s❡t ♦❢ ❝♦❧✉♠♥s ♦❢ t❤❡ v2k ∈ V2 =⇒ ck ∈ C .

I=1 j=i+1 k=1 l=k+1 fr (x) ✭✶✳✷✮ ✐s ❡q✉❛❧ t♦ ✵ ❢♦r ❛❧❧ G23,4 ✐♥ ❋✐❣✉r❡ ✶✳✷✳ ❍❡♥❝❡✱ G23,4 ✐s ❛ ■t ❝❛♥ ❜❡ ✈❡r✐✜❡❞ t❤❛t t❤❡ ❢✉♥❝t✐♦♥ ✶✽ ♣♦ss✐❜❧❡ r❡❝t❛♥❣❧❡s ♦❢ t❤❡ ❣r✐❞ r❡❝t❛♥❣❧❡✲❢r❡❡ ❣r✐❞ Grf 3,4 ✳ ❚❤❡ s♦❧✉t✐♦♥ ♦❢ t❤❡ ❇♦♦❧❡❛♥ ❡q✉❛t✐♦♥ ✭✶✳✸✮ ✐s t❤❡ s❡t ♦❢ ❛❧❧ r❡❝t❛♥❣❧❡✲ m r♦✇s ❛♥❞ n ❝♦❧✉♠♥s✳ ❚❤❡ ♥✉♠❜❡r ♦❢ ✈❛❧✉❡s ✶ ✐♥ s✉❝❤ ❛ n1 (Gm,n )✳ ❈♦✉♥t✐♥❣ t❤❡ ✈❛❧✉❡s ✶ ✐♥ t❤❡ ❣r✐❞s ♦❢ ❋✐❣✉r❡ ✶✳✷✱ ✇❡ 1 2 ❣❡t ❢♦r ❡①❛♠♣❧❡ n1 (G3,4 ) = 6 ❛♥❞ n1 (G3,4 ) = 7✳ ■t ✐s ♦✉r ✜♥❛❧ ❛✐♠ t♦ ✜♥❞ t❤❡ ✈❛❧✉❡✿ maxrf (m, n) ✇❤✐❝❤ ✐s t❤❡ ♠❛①✐♠❛❧ ♥✉♠❜❡r ♦❢ ✈❛❧✉❡s 1 ♦❢ ❛❧❧ r❡❝t❛♥❣❧❡✲❢r❡❡ ❣r✐❞s ♦❢ m r♦✇s ❛♥❞ n ❝♦❧✉♠♥s✿ ❢r❡❡ ❣r✐❞s ♦❢ ❣r✐❞ ✐s maxrf (m, n) = max n1 (Grf m,n ) .

Download PDF sample

Recent Progress in the Boolean Domain by Bernd Steinbach
Rated 4.08 of 5 – based on 13 votes