Complexity upper bounds using permutation group theory (Record no. 48812)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02153nam a2200253Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2006||||xx |||||||||||||| ||und|| |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Kurur, Piyush P. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Complexity upper bounds using permutation group theory |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2006 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | vi; 134p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2006 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | University of Madras |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | This thesis studies the Graph Isomorphism and problems that arise in Galois theory. It is targeted to use structural properties of permutation groups together with other algebraic techniques to prove complexity upper bounds. Complexity theory is the study of resource bounded computations. Efficiency is measured in terms of the resource required to solve the problem as a function of the input size. The study of complexity Graph Isomorphism and problems associated with Galois theory with an aim of classifying these in the frame work of complexity theory is undertaken. The role of permutation group theory is a common thread that connects these two. The structure of permutation groups and the numerous efficient algorithms for permutation group problems play an important role in this thesis results. Permutation groups also plays an important role in algorithms for Graph Isomorphism. Group theory has played an important role in various complexity theoretic results. Chapter 2 speaks about a brief survey of the complexity theory required for this thesis; Chapter 3 develops the required group theory. Chapter 6 describes the required algebraic number theory, from which some of the results leads to one of the results on Galois theory in this thesis. Chapters 4 and 5 explains the results on Graph Isomorphism and related problems. The results on computational problems in Galois theory is described in Chapters 7,8 and 9. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Complexity Theory |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Computational Galois Theory |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Graph Isomorphism |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Group Theory |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Arvind, V. |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/123 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|
| IMSc Library | http://www.imsc.res.in/xmlui/handle/123456789/123 | THESIS & DISSERTATION |