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 - it takes 3-4 days longer - 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. 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.