Problems of the class NP

Anatoly Plotnikov

ISBN 10: 3844393463 / ISBN 13: 9783844393460

Published by LAP LAMBERT Academic Publishing Mai 2011, 2011

About this Item

This item is printed on demand - Print on Demand Titel. Neuware -Problems of the class NP - it's almost all problems solved on the computer. Therefore, this is extremely important and actually to research the properties of such problems and to construct their mathematical models, which allows in a number of cases to improve the solution algorithms or propose new ones. In studying the problems of the class NP we focused on the NP-complete problems, the researching their properties and constructing models. We construct a mathematical model of constructive combinatorial problems, clarify the concept of a class of problems solved by a non-deterministic Turing machine and define the concept of the problem without foresight, investigate the set-theoretic properties of extreme combinatorial problems. We offer the polynomial-time algorithm for the maxumum independent set problem based on a hypotheses. Also, we find a criterion for Hamiltonicity of a graph and consider some covering problems. This book should be especially useful to professionals in computer sience.VDM Verlag, Dudweiler Landstraße 99, 66123 Saarbrücken 152 pp. Englisch.

Seller Inventory # 9783844393460

Bibliographic Details

• Title: Problems of the class NP
• Publisher: LAP LAMBERT Academic Publishing Mai 2011
• Publication Date: 2011
• Language: English
• ISBN 10: 3844393463
• ISBN 13: 9783844393460
• Binding: Taschenbuch
• Condition: Neu
• Dimensions: 220W x 150H x 10D millimeters 220 millimeters width by 150 millimeters height by 10 millimeters depth
• Weight: 244 grams

About this title

Synopsis

Problems of the class NP — it's almost all problems solved on the computer. Therefore, this is extremely important and actually to research the properties of such problems and to construct their mathematical models, which allows in a number of cases to improve the solution algorithms or propose new ones. In studying the problems of the class NP we focused on the NP-complete problems, the researching their properties and constructing models. We construct a mathematical model of constructive combinatorial problems, clarify the concept of a class of problems solved by a non-deterministic Turing machine and define the concept of the problem without foresight, investigate the set-theoretic properties of extreme combinatorial problems. We offer the polynomial-time algorithm for the maxumum independent set problem based on a hypotheses. Also, we find a criterion for Hamiltonicity of a graph and consider some covering problems. This book should be especially useful to professionals in computer sience.

About the Author

Anatoly Plotnikov is a professor of State University — the Dalh East-Ukrainian National University, Luhansk. He is also an associate member of AMS (USA) and a reviewer of the journal "Mathematical Reviews". His scientific interests include algorithms, combinatorial optimization, complexity theory.