cooks theorem

Cook’s Theorem:

Cook’s Theorem states that-
                                             Any NP problem can be converted to SAT in polynomial time.

In order to prove this, we require a uniform way of representing NP problems. Remember that what makes
a problem NP is the existence of a polynomial-time algorithm—more specifically, a Turing machine—for
checking candidate certificates. What Cook did was somewhat analogous to what Turing did when he
showed that the Entscheidungsproblem was equivalent to the Halting Problem. He showed how to encode
as Propositional Calculus clauses both the relevant facts about the problem instance and the Turing machine
which does the certificate-checking, in such a way that the resulting set of clauses is satisfiable if and only
if the original problem instance is positive. Thus the problem of determining the latter is reduced to the
problem of determining the former.
Assume, then, that we are given an NP decision problem D. By the definition of NP, there is a polyno-
mial function P and a Turing machine M which, when given any instance I of D, together with a candidate
certificate c, will check in time no greater than P (n), where n is the length of I, whether or not c is a
certificate of I.
Let us assume that M has q states numbered 0, 1, 2, . . . , q − 1, and a tape alphabet a1 , a2 , . . . , as . We
shall assume that the operation of the machine is governed by the functions T , U , and D as described in
the chapter on the Entscheidungsproblem. We shall further assume that the initial tape is inscribed with the
problem instance on the squares 1, 2, 3, . . . , n, and the putative certificate on the squares −m, . . . , −2, −1.
Square zero can be assumed to contain a designated separator symbol. We shall also assume that the machine
halts scanning square 0, and that the symbol in this square at that stage will be a1 if and only if the candidate
certificate is a true certificate. Note that we must have m ≤ P (n). This is because with a problem instance
of length n the computation is completed in at most P (n) steps; during this process, the Turing machine
head cannot move more than P (n) steps to the left of its starting point.
We define some atomic propositions with their intended interpretations as follows:

1. For i = 0, 1, . . . , P (n) and j = 0, 1, . . . , q − 1, the proposition Qij says that after i computation
steps, M is in state j.
2. For i = 0, 1, . . . , P (n), j = −P (n), . . . , P (n), and k = 1, 2, . . . , s, the proposition Sijk says that
after i computation steps, square j of the tape contains the symbol ak .

3. i = 0, 1, . . . , P (n) and j = −P (n), . . . , P (n), the proposition Tij says that after i computation steps,
the machine M is scanning square j of the tape.

Next, we define some clauses to describe the computation executed by M :

1. At each computation step, M is in at least one state. For each i = 0, . . . , P (n) we have the clause

Qi0 ∨ Qi1 ∨ · · · ∨ Qi(q−1) ,

giving (P (n) + 1)q = O(P (n)) literals altogether.

2. At each computation step, M is in at most one state. For each i = 0, . . . , P (n) and for each pair j, k
of distinct states, we have the clause
¬(Qij ∧ Qik ),

giving a total of q(q − 1)(P (n) + 1) = O(P (n)) literals altogether.

3. At each step, each tape square contains at least one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n) we have the clause

Sij1 ∨ Sij2 ∨ · · · ∨ Sijs ,

giving (P (n) + 1)(2P (n) + 1)s = O(P (n)2 ) literals altogether.

4. At each step, each tape square contains at most one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n), and each distinct pair ak , al of symbols we have the clause

¬(Sijk ∧ Sijl ),

giving a total of (P (n) + 1)(2P (n) + 1)s(s − 1) = O(P (n)2 ) literals altogether

5. At each step, the tape is scanning at least one square. For each i = 0, . . . , P (n), we have the clause

Ti(−P (n)) ∨ Ti(1−P (n)) ∨ · · · ∨ Ti(P (n)−1) ∨ TiP (n) ,

giving (P (n) + 1)(2P (n) + 1) = O(P (n)2 ) literals altogether.

6. At each step, the tape is scanning at most one square. For each i = 0, . . . , P (n), and each distinct
pair j, k of tape squares from −P (n) to P (n), we have the clause

¬(Tij ∧ Tik ),

giving a total of 2P (n)(2P (n) + 1)(P (n) + 1) = O(P (n)3 ) literals.

7. Initially, the machine is in state 1 scanning square 1. This is expressed by the two clauses

Q01 , T01 ,

giving just two literals.
8. The configuration at each step after the first is determined from the configuration at the previous step
by the functions T , U , and D defining the machine M . For each i = 0, . . . , P (n), −P (n) ≤ j ≤
P (n), k = 0, . . . , q − 1, and l = 1, . . . , s, we have the clauses

Tij ∧ Qik ∧ Sijl → Q(i+1)T (k,l)

Tij ∧ Qik ∧ Sijl → S(i+1)jU (k,l)

Tij ∧ Qik ∧ Sijl → T(i+1)(j+D(k,l))

Sijk → Tij ∨ S(i+1)jk

The fourth of these clauses ensures that the contents of any tape square other than the currently

Sijk ∧ ¬Tij → S(i+1)jk ). These clauses contribute a total of (12s + 3)(P (n) + 1)(2P (n) + 1)q =
O(P (n)2 ) literals.

9. Initially, the string ai1 ai2 . . . ain defining the problem instance I is inscribed on squares 1, 2, . . . , n
of the tape. This is expressed by the n clauses

S01i1 , S02i2 , . . . , S0nin ,

a total of n literals.

10. By the P (n)th step, the machine has reached the halt state, and is then scanning square 0, which
contains the symbol a1 . This is expressed by the three clauses

QP (n)0 , SP (n)01 , TP (n)0 ,

giving another 3 literals.

Altogether the number of literals involved in these clauses is O(P (n)3 ) (in working this out, note that q and
s are constants, that is, they depend only on the machine and do not vary with the problem instance; thus
they do not contribute to the growth of the the number of literals with increasing problem size, which is
what the O notation captures for us). It is thus clear that the procedure for setting up these clauses, given the
original machine M and the instance I of problem D, can be accomplished in polynomial time.
We must now show that we have succeeded in converting D into SAT . Suppose first that I is a positive
instance of D. This means that there is a certificate c such that when M is run with inputs c, I, it will halt
scanning symbol a1 on square 0. This means that there is some sequence of symbols that can be placed
initially on squares −P (n), . . . , −1 of the tape so that all the clauses above are satisfied. Hence those
clauses constitute a positive instance of SAT .
Conversely, suppose I is a negative instance of D. In that case there is no certificate for I, which means
that whatever symbols are placed on squares −P (n), . . . , −1 of the tape, when the computation halts the
machine will not be scanning a1 on square 0. This means that the set of clauses above is not satisfiable, and
hence constitutes a negative instance of SAT .
Thus from the instance I of problem D we have constructed, in polynomial time, a set of clauses which
constitute a positive instance of SAT if and only I is a positive instance of D. In other words, we have
converted D into SAT in polynomial time. And since D was an arbitrary NP problem it follows that any NP
problem can be converted to SAT in polynomial time.

Game tree(DAA)

Game tree

From Wikipedia, the free encyclopedia

Jump to: navigation, search

If you're looking for game tree as it's used in game theory (not combinatorial game theory), please see Extensive-form game.

In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position.

The first two ply of the game tree for tic-tac-toe.

The diagram shows the first two levels, or ply, in the game tree for tic-tac-toe. We consider all the rotations and reflections of positions as being equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on.
The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 26,830 leaf nodes.
Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many ply from the current position as it can search in the time available. Except for the case of "pathological" game trees ^[1] (which seem to be quite rare in practice), increasing the search depth (i.e., the number of ply searched) generally improves the chance of picking the best move.
Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Contents [hide] 1 Solving Game Trees 2 See also 3 References 3.1 Notes 3.2 General references

[edit] Solving Game Trees

An arbitrary game tree that has been fully colored

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee either a win or tie. The algorithm can be described recursively as follows.

1. Color the final ply of the game tree so that all wins for player 1 are colored one way, all wins for player 2 are colored another way, and all ties are colored a third way.
2. Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well. If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie.
3. Repeat for each ply, moving upwards, until all nodes are colored. The color of the root node will determine the nature of the game.

The diagram shows a game tree for an arbitrary game, colored using the above algorithm.
It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example alpha-beta pruning can be used in many deterministic games).
Any subtree that can be used to solve the game is known as a decision tree, and the sizes of decision trees of various shapes are used as measures of game complexity.^[2]

[edit] See also

• Alpha-beta pruning
• Extensive form game
• Shannon number
• Game complexity

[edit] References

[edit] Notes

1. ^ Nau, Dana (1982). "An investigation of the causes of pathology in games". Artificial Intelligence 19: 257–278. doi:10.1016/0004-3702(82)90002-9. 
2. ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880. http://fragrieu.free.fr/SearchingForSolutions.pdf. 

[edit] General references

• Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN 0486419622. http://books.google.com/?id=BF5_bCN72EUC. Retrieved 2007-04-02. 
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. Exploiting Graph Properties of Game Trees

Retrieved from "http://en.wikipedia.org/wiki/Game_tree"

Categories: Combinatorial game theory | Trees (graph theory)

 

 

source:

 http://en.wikipedia.org/wiki/Game_tree

Important Units to Study For External Exams 3-1

3-1 CSE/IT
AUTOMATA AND COMPILER DESIGN
Choose: Units I, II, III, VI, VII and VIII (1, 2, 3, 6, 7 and 8)

Formal Languages And Automata Theory
Choose: Units II, III, IV, V, VI and VII (2,3,4,5,6 and 7)
CLICK HERE FOR FLAT CHECK LIST
www.jntuworld.com
Computer Graphics : 1,2,3,6,8 Units

Micro Processor (MP) : 1,2,6,7,8 Units

Design and Analysis of Algorithms (DAA) : 1,2,3,4,5 Units

Software Testing Methodologies (STM) : 1,2,3,6,7 Units

Data Communication Systems (DCS) : 1,2,4,5,6 Units

Distributed Databases (DD) 1,2,3,5,6 Units




-by JNTU WORLD.
link:

http://forum.jntuworld.com/showthread.php?9796-Important-Units-to-Study-For-External-Exams

ayodhya land to be divided into 3 parts.....!!!!!

even i support tis judgment and put my hands together.
ALL R 1
v youth r ta building stones of our society.so,v have 2 respect ta judgment.
"2DAYS YOUTH R NEXT DAY CITIZENS"
but i personally believe tat............,,,,
"2DAYS YOUTH R 2DAYS CITIZENS &2DAY TEENS R 2MARROWS CITIZENS(YOUTH)"
i promise it , believe in it & live in it!!!..

how many of u agree wit me????????
post ur comments and express ur opinions

CLOUD COMPUTING

Cloud Computing vs Grid Computing

 

  

2009-2010 has been the year for new computing technology i.e Cloud Computing, as was the year 2007-2008 for SaaS-(Software as a Service). Cloud & grid Computing maybe considered opposites in terms of Functioning.Cloud Computing Assimilates everything into one place whereas GridComputing Divides everything.
So for those who wanna know here's a brief overview: 

 

 

 

 

 

 

 

 

Cloud computing is based on the principle of letting others do the work for

you, technically it means running all your Apps, documents & data from a third party 

server.Now, the question that people may ask is that, this have been done from long 

time & is nothing new, we have been using Apps from the net & storing our data 

online, So whats NEW?Well the ans is, that cloud computing not only stores our data 

online & provides us with Apps, but it also does the processing for us. The online

apps that we used before, used local processing upto some extend, But a cloud 

provides its own processing.

 

 

Now, from individual point of view this may not be of much significance, But for Large 

Organizations, which have huge data networks, Cloud is a boon, in a way that it 

saves them with the hassles of maintainence, s/w & h/w update & other hardware 

costs(as it doesnt rely on Host h/w or s/w), plus it saves time of the IT folks & 

helps them to deal with WHAT then to think about HOW.

Many may have concerns with security related issues that cloud computing may 

pose, bcoz for Corporations it amasses to huge amount of confidential & important 

data &it can be said that a Cloud is as safe as your email or any online account.
Many companies Like IBM, MICROSOFT & GOOGLE provide cloud based services.

There have been a lot of buzz of different possibilities & different experiments with 

cloud platform, for example European Union is carrying out research studies on 

the possibility of providing Cloud based Gaming & other ON-DEMAND services.

GridComputing on the other hand is something exact opposite, cloud does 

the processing for you, Grid needs processing from you. Grid computing has mostly 

used by scientific &research based Organizations & Universities round the world.
Its based on the CLIENT-SERVER model. In a Grid there are 

several thousand (may be more) computers connected as nodes to a central 

server(maybe more than one server). 

The processing of data such as scientific analysis or Disease based research, is 

divided & distributed over the nodes. The node provides the processing power, while 

the server just distributes, assimilates & administers the process.
A single Grid can provide computing power Equivalent to a SUPER Computer, For 

example THE WORLD COMMUNITY GRID, which researches on cures for Diseases 

such as Cancer, Aids etc has 475,000 registered user &  Computing power equal to 

approx 3.3 teraflops.Concept of Grid Computing has also been used in the 

underground world for stealing data & spreading malware, The Zeus Botnet, The 

Torpig Botnet are similar to concepts of grid computing, though not entirely similar.

IEEE format rules 4 ppts

                          FORMAT FOR FULL LENGTH PAPER

                     Author Guidelines for 8.5x11-inch Proceedings Manuscripts

Author(s) Name(s)
Author Affiliation(s)
E-mail



Abstract

The abstract is to be in fully-justified italicized text, at the top of the left-hand column as it is here, below the author information. Use the word “Abstract” as the title, in 12-point Times, boldface type, centered relative to the column, initially capitalized. The abstract is to be in 10-point, single-spaced type, and may be up to 3 in. (7.62 cm) long. Leave two blank lines after the abstract, then begin the main text. All manuscripts must be in English.

1. Introduction

These guidelines include complete descriptions of the fonts, spacing, and related information for producing your proceedings manuscripts. Please follow them.

2. Formatting your paper

All printed material, including text, illustrations, and charts, must be kept within a print area of 6-7/8 inches (17.5 cm) wide by 8-7/8 inches (22.54 cm) high. Do not write or print anything outside the print area. All text must be in a two-column format. Columns are to be 3-1/4 inches (8.25 cm) wide, with a 5/16 inch (0.8 cm) space between them. Text must be fully justified.
A format sheet with the margins and placement guides is available in Word as . It contains lines and boxes showing the margins and print areas. If you hold it and your printed page up to the light, you can easily check your margins to see if your print area fits within the space allowed.

3. Main title

The main title (on the first page) should begin 1-3/8 inches (3.49 cm) from the top edge of the page, centered, and in Times 14-point, boldface type. Capitalize the first letter of nouns, pronouns, verbs, adjectives, and adverbs; do not capitalize articles, coordinate conjunctions, or prepositions (unless the title begins with such a word). Leave two blank lines after the title.

4. Author name(s) and affiliation(s)

Author names and affiliations are to be centered beneath the title and printed in Times 12-point, non-boldface type. Multiple authors may be shown in a two- or three-column format, with their affiliations below their respective names. Affiliations are centered below each author name, italicized, not bold. Include e-mail addresses if possible. Follow the author information by two blank lines before main text.

5. Second and following pages

The second and following pages should begin 1.0 inch (2.54 cm) from the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86 cm) from the bottom edge of the page for 8.5 x 11-inch paper; for A4 paper, approximately 1-5/8 inches (4.13 cm) from the bottom edge of the page.

6. Type-style and fonts

Wherever Times is specified, Times Roman, or New Times Roman may be used. If neither is available on your word processor, please use the font closest in appearance to Times that you have access to. Please avoid using bit-mapped fonts if possible. True-Type 1 fonts are preferred.

7. Main text

Type your main text in 10-point Times, single-spaced. Do not use double-spacing. All paragraphs should be indented 1 pica (approximately 1/6- or 0.17-inch or 0.422 cm). Be sure your text is fully justified—that is, flush left and flush right. Please do not place any additional blank lines between paragraphs.
Figure and table captions should be 10-point Helvetica (or a similar sans-serif font), boldface. Callouts should be 9-point Helvetica, non-boldface. Initially capitalize only the first word of each figure caption and table title. Figures and tables must be numbered separately. For example: “Figure 1. Database contexts”, “Table 1. Input data”. Figure captions are to be below the figures. Table titles are to be centered above the tables.

8. First-order headings

For example, “1. Introduction”, should be Times 12-point boldface, initially capitalized, flush left, with one blank line before, and one blank line after. Use a period (“.”) after the heading number, not a colon.

8.1. Second-order headings

As in this heading, they should be Times 11-point boldface, initially capitalized, flush left, with one blank line before, and one after.

8.1.1. Third-order headings. Third-order headings, as in this paragraph, are discouraged. However, if you must use them, use 10-point Times, boldface, initially capitalized, flush left, preceded by one blank line, followed by a period and your text on the same line.

9. Footnotes

Use footnotes sparingly (or not at all!) and place them at the bottom of the column on the page on which they are referenced. Use Times 8-point type, single-spaced. To help your readers, avoid using footnotes altogether and include necessary peripheral observations in the text (within parentheses, if you prefer, as in this sentence).

10. References

List and number all bibliographical references in 9-point Times, single-spaced, at the end of your paper. When referenced in the text, enclose the citation number in square brackets, for example [1]. Where appropriate, include the name(s) of editors of referenced books.

[1] A.B. Smith, C.D. Jones, and E.F. Roberts, “Article Title”, Journal, Publisher, Location, Date, pp. 1-10.

[2] Jones, C.D., A.B. Smith, and E.F. Roberts, Book Title, Publisher, Location, Date.

MPI LAB MANUAL

JAWAHAR LAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. CSE -I Sem T P C
0 3 2
MICROPROCESSORS INTERFACING LAB
I. Microprocessor 8086 :
1. Introduction to MASM/TASM.
2. Arithmetic operation – Multi byte Addition and Subtraction, Multiplication and Division – Signed and unsigned Arithmetic operation, ASCII – arithmetic operation.
3. Logic operations – Shift and rotate – Converting packed BCD to unpacked BCD, BCD to ASCII conversion.
4. By using string operation and Instruction prefix: Move Block, Reverse string, Sorting, Inserting, Deleting, Length of the string, String comparison.
5. DOS/BIOS programming: Reading keyboard (Buffered with and without echo) – Display characters, Strings.

II. Interfacing :
1. 8259 – Interrupt Controller : Generate an interrupt using 8259 timer.
2. 8279 – Keyboard Display : Write a small program to display a string of characters.
3. 8255 – PPI : Write ALP to generate sinusoidal wave using PPI.
4. 8251 – USART : Write a program in ALP to establish Communication between two processors.

III. Microcontroller 8051
1. Reading and Writing on a parallel port.
2. Timer in different modes.
3. Serial communication implementation.


Equipment required for Laboratories:
1. 8086 µP Kits
2. 8051 Micro Controller kits
3. Interfaces/peripheral subsystems
i) 8259 PIC
ii) 8279-KB/Display
iii) 8255 PPI
iv) 8251 USART

4. ADC Interface
5. DAC Interface
6. Traffic Controller Interface
7. Elevator Interface