{"id":476352,"date":"2023-08-09T07:28:31","date_gmt":"2023-08-09T07:28:31","guid":{"rendered":""},"modified":"2023-09-05T11:12:34","modified_gmt":"2023-09-05T11:12:34","slug":"computational-complexity-theory","status":"publish","type":"wiki","link":"https:\/\/oneproxy.pro\/ir\/wiki\/computational-complexity-theory\/","title":{"rendered":"\u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc"},"content":{"rendered":"<p>\u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0634\u0627\u062e\u0647 \u0627\u06cc \u0627\u0632 \u0639\u0644\u0648\u0645 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631 \u0627\u0633\u062a \u06a9\u0647 \u0645\u0646\u0627\u0628\u0639 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0645\u0633\u0627\u0626\u0644 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0645\u0637\u0627\u0644\u0639\u0647 \u0645\u06cc \u06a9\u0646\u062f. \u0627\u06cc\u0646 \u06cc\u06a9 \u0627\u0646\u062a\u0632\u0627\u0639 \u0631\u06cc\u0627\u0636\u06cc \u0627\u0632 \u0633\u062e\u062a\u200c\u0627\u0641\u0632\u0627\u0631 \u0631\u0627\u06cc\u0627\u0646\u0647 \u0648 \u062a\u062c\u0632\u06cc\u0647 \u0648 \u062a\u062d\u0644\u06cc\u0644 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u200c\u0647\u0627 \u0631\u0627 \u0627\u0631\u0627\u0626\u0647 \u0645\u06cc\u200c\u06a9\u0646\u062f \u0648 \u0622\u0646 \u0631\u0627 \u0628\u0647 \u06cc\u06a9 \u062c\u0632\u0621 \u062d\u06cc\u0627\u062a\u06cc \u062f\u0631 \u062f\u0631\u06a9 \u0648 \u0627\u0631\u0632\u06cc\u0627\u0628\u06cc \u06a9\u0627\u0631\u0627\u06cc\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u200c\u0647\u0627 \u0648 \u0645\u062d\u062f\u0648\u062f\u06cc\u062a\u200c\u0647\u0627\u06cc \u06a9\u0627\u0631\u06cc \u06a9\u0647 \u0631\u0627\u06cc\u0627\u0646\u0647\u200c\u0647\u0627 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u0646\u062f \u0627\u0646\u062c\u0627\u0645 \u062f\u0647\u0646\u062f \u062a\u0628\u062f\u06cc\u0644 \u0645\u06cc\u200c\u06a9\u0646\u062f.<\/p>\n<h2>\u067e\u06cc\u062f\u0627\u06cc\u0634 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<p>\u0638\u0647\u0648\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0628\u0647 \u0639\u0646\u0648\u0627\u0646 \u06cc\u06a9 \u0632\u0645\u06cc\u0646\u0647 \u0645\u062a\u0645\u0627\u06cc\u0632 \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u062f\u0647\u0647 1950 \u0648 1960 \u0631\u062f\u06cc\u0627\u0628\u06cc \u06a9\u0631\u062f. \u0628\u0627 \u0627\u06cc\u0646 \u062d\u0627\u0644\u060c \u0627\u0635\u0648\u0644 \u0632\u06cc\u0631\u0628\u0646\u0627\u06cc\u06cc \u0622\u0646 \u0627\u0632 \u0632\u0645\u0627\u0646 \u067e\u06cc\u062f\u0627\u06cc\u0634 \u0639\u0644\u0645 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631 \u0646\u0638\u0631\u06cc \u0648 \u0646\u0638\u0631\u06cc\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0631 \u062d\u0627\u0644 \u062a\u0648\u0633\u0639\u0647 \u0628\u0648\u062f. \u0645\u0647\u0645 \u062a\u0631\u06cc\u0646 \u0646\u0642\u0637\u0647 \u0639\u0637\u0641 \u062f\u0631 \u0633\u0627\u0644 1965 \u0632\u0645\u0627\u0646\u06cc \u06a9\u0647 \u062c\u0648\u0631\u06cc\u0633 \u0647\u0627\u0631\u062a\u0645\u0627\u0646\u06cc\u0633 \u0648 \u0631\u06cc\u0686\u0627\u0631\u062f \u0627\u0633\u062a\u0631\u0646\u0632 \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc P (\u0632\u0645\u0627\u0646 \u0686\u0646\u062f \u062c\u0645\u0644\u0647 \u0627\u06cc) \u0648 EXP (\u0632\u0645\u0627\u0646 \u0646\u0645\u0627\u06cc\u06cc) \u0631\u0627 \u067e\u06cc\u0634\u0646\u0647\u0627\u062f \u06a9\u0631\u062f\u0646\u062f \u0648 \u0645\u0637\u0627\u0644\u0639\u0647 \u0631\u0633\u0645\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0622\u063a\u0627\u0632 \u06a9\u0631\u062f\u0646\u062f. \u06a9\u0627\u0631 \u0622\u0646\u0647\u0627 \u062c\u0627\u06cc\u0632\u0647 \u062a\u0648\u0631\u06cc\u0646\u06af \u0631\u0627 \u062f\u0631 \u0633\u0627\u0644 1993 \u0628\u0647 \u0627\u0631\u0645\u063a\u0627\u0646 \u0622\u0648\u0631\u062f.<\/p>\n<p>\u0645\u0633\u0626\u0644\u0647 P \u062f\u0631 \u0645\u0642\u0627\u0628\u0644 NP\u060c \u06cc\u06a9\u06cc \u0627\u0632 \u0645\u0639\u0631\u0648\u0641 \u062a\u0631\u06cc\u0646 \u0645\u0633\u0627\u0626\u0644 \u062d\u0644 \u0646\u0634\u062f\u0647 \u062f\u0631 \u0639\u0644\u0648\u0645 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631\u060c \u0627\u0648\u0644\u06cc\u0646 \u0628\u0627\u0631 \u062a\u0648\u0633\u0637 \u062c\u0627\u0646 \u0646\u0634 \u062f\u0631 \u0633\u0627\u0644 1955 \u0630\u06a9\u0631 \u0634\u062f \u0648 \u0628\u0639\u062f\u0627\u064b \u062a\u0648\u0633\u0637 \u0627\u0633\u062a\u06cc\u0648\u0646 \u06a9\u0648\u06a9 \u0648 \u0644\u0626\u0648\u0646\u06cc\u062f \u0644\u0648\u06cc\u0646 \u0628\u0647 \u0637\u0648\u0631 \u0645\u0633\u062a\u0642\u0644 \u062f\u0631 \u0633\u0627\u0644 1971 \u0631\u0633\u0645\u06cc\u062a \u06cc\u0627\u0641\u062a. \u0627\u06cc\u0646 \u0645\u0633\u0626\u0644\u0647 \u06a9\u0647 \u0627\u0633\u0627\u0633\u0627\u064b \u062f\u0631 \u0645\u0648\u0631\u062f \u0631\u0627\u0628\u0637\u0647 \u0628\u06cc\u0646 \u0645\u0633\u0627\u0626\u0644 \u0627\u0633\u062a. \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u0633\u0631\u0639\u062a \u062d\u0644 \u06a9\u0631\u062f \u0648 \u0622\u0646\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0631\u0627\u0647 \u062d\u0644 \u0647\u0627 \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u0633\u0631\u0639\u062a \u0628\u0631\u0631\u0633\u06cc \u06a9\u0631\u062f\u060c \u0628\u0633\u06cc\u0627\u0631\u06cc \u0627\u0632 \u062a\u062d\u0642\u06cc\u0642\u0627\u062a \u062f\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0647\u062f\u0627\u06cc\u062a \u06a9\u0631\u062f\u0647 \u0627\u0633\u062a.<\/p>\n<h2>\u063a\u0648\u0627\u0635\u06cc \u0639\u0645\u06cc\u0642 \u062f\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<p>\u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u062f\u0631 \u0645\u0648\u0631\u062f \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u0642\u062f\u0627\u0631 \u0645\u0646\u0627\u0628\u0639 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc - \u0645\u0627\u0646\u0646\u062f \u0632\u0645\u0627\u0646\u060c \u062d\u0627\u0641\u0638\u0647 \u0648 \u0627\u0631\u062a\u0628\u0627\u0637\u0627\u062a - \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u062d\u0644 \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0627\u0633\u062a. \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0628\u0631 \u062d\u0633\u0628 \u0645\u0646\u0627\u0628\u0639 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0647\u062a\u0631\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0645\u06a9\u0646 \u06a9\u0647 \u0645\u0634\u06a9\u0644 \u0631\u0627 \u062d\u0644 \u0645\u06cc \u06a9\u0646\u062f\u060c \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u0634\u0648\u062f.<\/p>\n<p>\u0628\u0631\u0627\u06cc \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u06cc\u06a9 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u060c \u0645\u0639\u0645\u0648\u0644\u0627\u064b \u06cc\u06a9 \u0627\u0646\u062f\u0627\u0632\u0647 \u0648\u0631\u0648\u062f\u06cc (\u0645\u0639\u0645\u0648\u0644\u0627\u064b \u062a\u0639\u062f\u0627\u062f \u0628\u06cc\u062a \u0647\u0627\u06cc \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u0646\u0645\u0627\u06cc\u0634 \u0648\u0631\u0648\u062f\u06cc) \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc \u0634\u0648\u062f \u0648 \u0645\u0646\u0628\u0639 \u0628\u0647 \u0639\u0646\u0648\u0627\u0646 \u062a\u0627\u0628\u0639\u06cc \u0627\u0632 \u0627\u0646\u062f\u0627\u0632\u0647 \u0648\u0631\u0648\u062f\u06cc \u062a\u0648\u0635\u06cc\u0641 \u0645\u06cc \u0634\u0648\u062f. \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u0633\u0627\u0626\u0644 \u0631\u0627 \u0628\u0631 \u0627\u0633\u0627\u0633 \u0645\u0642\u062f\u0627\u0631 \u0645\u0646\u0628\u0639 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u062e\u0627\u0635 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0622\u0646\u0647\u0627 \u062f\u0633\u062a\u0647 \u0628\u0646\u062f\u06cc \u0645\u06cc \u06a9\u0646\u0646\u062f. \u0646\u0645\u0648\u0646\u0647\u200c\u0647\u0627\u06cc\u06cc \u0627\u0632 \u06a9\u0644\u0627\u0633\u200c\u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0639\u0628\u0627\u0631\u062a\u0646\u062f \u0627\u0632 P (\u0645\u0633\u0627\u0626\u0644 \u0642\u0627\u0628\u0644 \u062d\u0644 \u062f\u0631 \u0632\u0645\u0627\u0646 \u0686\u0646\u062f \u062c\u0645\u0644\u0647\u200c\u0627\u06cc)\u060c NP (\u0645\u0634\u06a9\u0644\u0627\u062a\u06cc \u06a9\u0647 \u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627\u06cc \u0622\u0646\u200c\u0647\u0627 \u0631\u0627 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062f\u0631 \u0632\u0645\u0627\u0646 \u0686\u0646\u062f \u062c\u0645\u0644\u0647\u200c\u0627\u06cc \u0628\u0631\u0631\u0633\u06cc \u06a9\u0631\u062f)\u060c \u0648 NP-complete (\u0645\u0634\u06a9\u0644\u0627\u062a\u06cc \u06a9\u0647 \u0647\u0631 \u0645\u0633\u0626\u0644\u0647 NP \u0631\u0627 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062f\u0631 \u0632\u0645\u0627\u0646 \u0686\u0646\u062f \u062c\u0645\u0644\u0647\u200c\u0627\u06cc \u06a9\u0627\u0647\u0634 \u062f\u0627\u062f).<\/p>\n<p>\u0646\u06af\u0631\u0627\u0646\u06cc \u0627\u0635\u0644\u06cc \u062f\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc\u060c \u062a\u0639\u06cc\u06cc\u0646 \u062f\u0634\u0648\u0627\u0631\u06cc \u0630\u0627\u062a\u06cc \u0645\u0633\u0627\u0626\u0644 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0627\u0633\u062a \u06a9\u0647 \u0627\u063a\u0644\u0628\u060c \u0627\u0645\u0627 \u0646\u0647 \u0647\u0645\u06cc\u0634\u0647\u060c \u0628\u0631 \u062d\u0633\u0628 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u0628\u06cc\u0627\u0646 \u0645\u06cc\u200c\u0634\u0648\u062f. \u0627\u06af\u0631 \u0628\u0627 \u0627\u0641\u0632\u0627\u06cc\u0634 \u0627\u0646\u062f\u0627\u0632\u0647 \u0648\u0631\u0648\u062f\u06cc\u060c \u0632\u0645\u0627\u0646 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0622\u0646 \u0628\u0647 \u0633\u0631\u0639\u062a \u0627\u0641\u0632\u0627\u06cc\u0634 \u06cc\u0627\u0628\u062f\u060c \u06cc\u06a9 \u0645\u0634\u06a9\u0644 &quot;\u0633\u062e\u062a&quot; \u062f\u0631 \u0646\u0638\u0631 \u06af\u0631\u0641\u062a\u0647 \u0645\u06cc \u0634\u0648\u062f.<\/p>\n<h2>\u0645\u06a9\u0627\u0646\u06cc\u06a9 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<p>\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0628\u0627 \u0633\u0627\u062e\u062a \u0645\u062f\u0644 \u0647\u0627\u06cc \u0631\u06cc\u0627\u0636\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a \u0648 \u0633\u067e\u0633 \u062a\u062c\u0632\u06cc\u0647 \u0648 \u062a\u062d\u0644\u06cc\u0644 \u0627\u06cc\u0646 \u0645\u062f\u0644 \u0647\u0627 \u062a\u0639\u06cc\u06cc\u0646 \u0645\u06cc \u0634\u0648\u062f. \u0645\u062a\u062f\u0627\u0648\u0644 \u062a\u0631\u06cc\u0646 \u0645\u062f\u0644 \u0645\u0627\u0634\u06cc\u0646 \u062a\u0648\u0631\u06cc\u0646\u06af \u0627\u0633\u062a\u060c \u0645\u0627\u0634\u06cc\u0646\u06cc \u0627\u0646\u062a\u0632\u0627\u0639\u06cc \u06a9\u0647 \u0646\u0645\u0627\u062f\u0647\u0627 \u0631\u0627 \u0628\u0631 \u0631\u0648\u06cc \u06cc\u06a9 \u0646\u0648\u0627\u0631 \u0646\u0648\u0627\u0631 \u0628\u0631 \u0627\u0633\u0627\u0633 \u0645\u062c\u0645\u0648\u0639\u0647 \u0627\u06cc \u0645\u062d\u062f\u0648\u062f \u0627\u0632 \u0642\u0648\u0627\u0646\u06cc\u0646 \u062f\u0633\u062a\u06a9\u0627\u0631\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<p>\u06cc\u06a9\u06cc \u0627\u0632 \u062c\u0646\u0628\u0647 \u0647\u0627\u06cc \u0627\u0633\u0627\u0633\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc\u060c \u0645\u0641\u0647\u0648\u0645 \u00ab\u06a9\u0644\u0627\u0633\u00bb \u0645\u0633\u0626\u0644\u0647 \u0627\u0633\u062a \u06a9\u0647 \u0645\u062c\u0645\u0648\u0639\u0647 \u0627\u06cc \u0627\u0632 \u0645\u0633\u0627\u0626\u0644 \u0628\u0627 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u0628\u062a\u0646\u06cc \u0628\u0631 \u0645\u0646\u0627\u0628\u0639 \u0645\u0631\u062a\u0628\u0637 \u0627\u0633\u062a. \u0647\u0645\u0627\u0646\u0637\u0648\u0631 \u06a9\u0647 \u0642\u0628\u0644\u0627 \u0630\u06a9\u0631 \u0634\u062f\u060c P\u060c NP \u0648 NP-complete \u0646\u0645\u0648\u0646\u0647 \u0647\u0627\u06cc\u06cc \u0627\u0632 \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u0645\u0633\u0626\u0644\u0647 \u0647\u0633\u062a\u0646\u062f. \u0637\u0628\u0642\u0647 \u0628\u0646\u062f\u06cc \u0645\u0633\u0627\u0626\u0644 \u0628\u0647 \u0627\u06cc\u0646 \u0631\u0648\u0634 \u0628\u0647 \u062a\u0634\u0631\u06cc\u062d \u0686\u0634\u0645 \u0627\u0646\u062f\u0627\u0632 \u0627\u06cc\u0646\u06a9\u0647 \u0686\u0647 \u0686\u06cc\u0632\u06cc \u0627\u0632 \u0646\u0638\u0631 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0627\u0645\u06a9\u0627\u0646 \u067e\u0630\u06cc\u0631 \u0627\u0633\u062a \u0648 \u0686\u0647 \u0686\u06cc\u0632\u06cc \u063a\u06cc\u0631\u0645\u0645\u06a9\u0646 \u0627\u0633\u062a\u060c \u06a9\u0645\u06a9 \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<h2>\u0648\u06cc\u0698\u06af\u06cc \u0647\u0627\u06cc \u06a9\u0644\u06cc\u062f\u06cc \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<ol>\n<li>\n<p><strong>\u0637\u0628\u0642\u0647 \u0628\u0646\u062f\u06cc \u0645\u0634\u06a9\u0644\u0627\u062a<\/strong>: \u062a\u0626\u0648\u0631\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0645\u0633\u0627\u0626\u0644 \u0631\u0627 \u0628\u0631 \u0627\u0633\u0627\u0633 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0628\u0647 \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641\u06cc \u0637\u0628\u0642\u0647 \u0628\u0646\u062f\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<\/li>\n<li>\n<p><strong>\u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u0635\u0631\u0641 \u0645\u0646\u0627\u0628\u0639<\/strong>: \u06cc\u06a9 \u0631\u0648\u06cc\u06a9\u0631\u062f \u0631\u06cc\u0627\u0636\u06cc \u0628\u0631\u0627\u06cc \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u0646\u0627\u0628\u0639 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u06cc\u06a9 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0627\u0631\u0627\u0626\u0647 \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<\/li>\n<li>\n<p><strong>\u0645\u0634\u06a9\u0644 \u0630\u0627\u062a\u06cc \u0645\u0634\u06a9\u0644<\/strong>: \u062f\u0634\u0648\u0627\u0631\u06cc \u0630\u0627\u062a\u06cc \u0645\u0633\u0627\u0626\u0644 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0628\u062f\u0648\u0646 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0645\u0648\u0631\u062f \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0622\u0646\u0647\u0627 \u0628\u0631\u0631\u0633\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<\/li>\n<li>\n<p><strong>\u0645\u062d\u062f\u0648\u062f\u06cc\u062a \u0647\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/strong>: \u0628\u0647 \u062f\u0646\u0628\u0627\u0644 \u062a\u0639\u06cc\u06cc\u0646 \u0645\u0631\u0632\u0647\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0645\u0645\u06a9\u0646 \u0648 \u063a\u06cc\u0631\u0645\u0645\u06a9\u0646 \u0627\u0633\u062a.<\/p>\n<\/li>\n<li>\n<p><strong>\u0645\u0639\u0627\u062f\u0644 \u0633\u0627\u0632\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/strong>: \u0645\u0639\u0627\u062f\u0644\u0627\u062a \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0628\u0627 \u0646\u0634\u0627\u0646 \u062f\u0627\u062f\u0646 \u0686\u06af\u0648\u0646\u06af\u06cc \u062a\u0628\u062f\u06cc\u0644 \u06cc\u0627 \u06a9\u0627\u0647\u0634 \u0645\u0633\u0627\u0626\u0644 \u0645\u062e\u062a\u0644\u0641 \u0628\u0647 \u06cc\u06a9\u062f\u06cc\u06af\u0631 \u0646\u0634\u0627\u0646 \u0645\u06cc \u062f\u0647\u062f.<\/p>\n<\/li>\n<\/ol>\n<h2>\u0627\u0646\u0648\u0627\u0639 \u0645\u062e\u062a\u0644\u0641 \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc<\/h2>\n<p>\u0631\u0648\u0634 \u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641\u06cc \u0628\u0631\u0627\u06cc \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u0648 \u0647\u0631 \u0646\u0648\u0639 \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u0645\u06a9\u0646 \u0627\u0633\u062a \u0628\u0627 \u06a9\u0644\u0627\u0633 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062a\u0641\u0627\u0648\u062a\u06cc \u0645\u0637\u0627\u0628\u0642\u062a \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align: center;\">\u062a\u0627\u06cc\u067e \u06a9\u0646\u06cc\u062f<\/th>\n<th style=\"text-align: center;\">\u0634\u0631\u062d<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc<\/td>\n<td style=\"text-align: center;\">\u0632\u0645\u0627\u0646 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0631\u0627 \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0641\u0636\u0627<\/td>\n<td style=\"text-align: center;\">\u0645\u0642\u062f\u0627\u0631 \u062d\u0627\u0641\u0638\u0647 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0634\u062f\u0647 \u062a\u0648\u0633\u0637 \u06cc\u06a9 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0631\u0627 \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0627\u0631\u062a\u0628\u0627\u0637\u0627\u062a<\/td>\n<td style=\"text-align: center;\">\u0645\u06cc\u0632\u0627\u0646 \u0627\u0631\u062a\u0628\u0627\u0637 \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632 \u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a \u062a\u0648\u0632\u06cc\u0639 \u0634\u062f\u0647 \u0631\u0627 \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u06cc \u06a9\u0646\u062f.<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062f\u0627\u0631<\/td>\n<td style=\"text-align: center;\">\u0627\u0646\u062f\u0627\u0632\u0647 \u06cc\u06a9 \u0645\u062f\u0627\u0631 \u0628\u0648\u0644\u06cc \u0631\u0627 \u0627\u0646\u062f\u0627\u0632\u0647 \u0645\u06cc \u06af\u06cc\u0631\u062f \u06a9\u0647 \u0645\u0634\u06a9\u0644 \u0631\u0627 \u062d\u0644 \u0645\u06cc \u06a9\u0646\u062f.<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u062f\u0631\u062e\u062a \u062a\u0635\u0645\u06cc\u0645<\/td>\n<td style=\"text-align: center;\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0631\u0627 \u062f\u0631 \u0645\u062f\u0644\u06cc \u0627\u0646\u062f\u0627\u0632\u0647 \u06af\u06cc\u0631\u06cc \u0645\u06cc \u06a9\u0646\u062f \u06a9\u0647 \u062f\u0631 \u0622\u0646 \u06cc\u06a9 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631 \u0641\u0642\u0637 \u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u062a\u0635\u0645\u06cc\u0645\u0627\u062a \u0628\u0627\u06cc\u0646\u0631\u06cc \u0633\u0627\u062f\u0647 \u0628\u06af\u06cc\u0631\u062f.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>\u06a9\u0627\u0631\u0628\u0631\u062f\u0647\u0627\u060c \u0686\u0627\u0644\u0634 \u0647\u0627 \u0648 \u0631\u0627\u0647 \u062d\u0644 \u0647\u0627 \u062f\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<p>\u0627\u06cc\u0646 \u0646\u0638\u0631\u06cc\u0647 \u06a9\u0627\u0631\u0628\u0631\u062f\u0647\u0627\u06cc \u06af\u0633\u062a\u0631\u062f\u0647 \u0627\u06cc \u062f\u0631 \u0637\u0631\u0627\u062d\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u060c \u0631\u0645\u0632\u0646\u06af\u0627\u0631\u06cc\u060c \u0633\u0627\u062e\u062a\u0627\u0631\u0647\u0627\u06cc \u062f\u0627\u062f\u0647 \u0648 \u063a\u06cc\u0631\u0647 \u062f\u0627\u0631\u062f. \u0628\u0627 \u0627\u0631\u0627\u0626\u0647 \u06cc\u06a9 \u062d\u062f \u0628\u0627\u0644\u0627\u06cc\u06cc \u062f\u0631 \u0645\u0646\u0627\u0628\u0639 \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0645\u0648\u0631\u062f \u0646\u06cc\u0627\u0632\u060c \u0628\u0647 \u0637\u0631\u0627\u062d\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0647\u0627\u06cc \u06a9\u0627\u0631\u0622\u0645\u062f \u06a9\u0645\u06a9 \u0645\u06cc \u06a9\u0646\u062f.<\/p>\n<p>\u06cc\u06a9 \u0686\u0627\u0644\u0634 \u0628\u0632\u0631\u06af \u062f\u0631 \u0627\u06cc\u0646 \u0632\u0645\u06cc\u0646\u0647\u060c \u0641\u0642\u062f\u0627\u0646 \u06cc\u06a9 \u0627\u062b\u0628\u0627\u062a \u0631\u0633\u0645\u06cc \u0628\u0631\u0627\u06cc \u0628\u0631\u062e\u06cc \u0627\u0632 \u0645\u0647\u0645 \u062a\u0631\u06cc\u0646 \u0633\u0624\u0627\u0644\u0627\u062a\u060c \u0645\u0627\u0646\u0646\u062f \u0645\u0633\u0626\u0644\u0647 P \u062f\u0631 \u0645\u0642\u0627\u0628\u0644 NP \u0627\u0633\u062a. \u0628\u0627 \u0648\u062c\u0648\u062f \u0627\u06cc\u0646 \u0686\u0627\u0644\u0634 \u0647\u0627\u060c \u062a\u0648\u0633\u0639\u0647 \u0648 \u0627\u0635\u0644\u0627\u062d \u0645\u062f\u0627\u0648\u0645 \u062a\u06a9\u0646\u06cc\u06a9 \u0647\u0627\u06cc \u0627\u062b\u0628\u0627\u062a\u060c \u0645\u062f\u0644 \u0647\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0648 \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0628\u0647 \u0637\u0648\u0631 \u067e\u06cc\u0648\u0633\u062a\u0647 \u062f\u0631\u06a9 \u0645\u0627 \u0631\u0627 \u0627\u0632 \u0645\u062d\u062f\u0648\u062f\u06cc\u062a \u0647\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u06af\u0633\u062a\u0631\u0634 \u0645\u06cc \u062f\u0647\u062f.<\/p>\n<h2>\u0645\u0642\u0627\u06cc\u0633\u0647 \u0647\u0627 \u0648 \u0648\u06cc\u0698\u06af\u06cc \u0647\u0627\u06cc \u06a9\u0644\u06cc\u062f\u06cc<\/h2>\n<p>\u0645\u0642\u0627\u06cc\u0633\u0647 \u0628\u06cc\u0646 \u06a9\u0644\u0627\u0633\u200c\u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062e\u062a\u0644\u0641\u060c \u0645\u062d\u0648\u0631 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u062a\u0634\u06a9\u06cc\u0644 \u0645\u06cc\u200c\u062f\u0647\u062f.<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align: center;\">\u06a9\u0644\u0627\u0633<\/th>\n<th style=\"text-align: center;\">\u0634\u0631\u062d<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align: center;\">\u067e<\/td>\n<td style=\"text-align: center;\">\u0645\u0633\u0627\u0626\u0644\u06cc \u06a9\u0647 \u0628\u0647 \u0633\u0631\u0639\u062a \u0642\u0627\u0628\u0644 \u062d\u0644 \u0647\u0633\u062a\u0646\u062f (\u062f\u0631 \u0632\u0645\u0627\u0646 \u0686\u0646\u062f \u062c\u0645\u0644\u0647 \u0627\u06cc)<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">NP<\/td>\n<td style=\"text-align: center;\">\u0645\u0634\u06a9\u0644\u0627\u062a\u06cc \u06a9\u0647 \u067e\u0633 \u0627\u0632 \u0627\u0631\u0627\u0626\u0647 \u0631\u0627\u0647 \u062d\u0644\u060c \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0647 \u0633\u0631\u0639\u062a \u0628\u0631\u0631\u0633\u06cc \u06a9\u0631\u062f<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">NP-\u06a9\u0627\u0645\u0644<\/td>\n<td style=\"text-align: center;\">\u0633\u062e\u062a \u062a\u0631\u06cc\u0646 \u0645\u0634\u06a9\u0644\u0627\u062a \u062f\u0631 NP; \u06cc\u06a9 \u0631\u0627\u0647 \u062d\u0644 \u0628\u0631\u0627\u06cc \u06cc\u06a9\u06cc \u0631\u0627 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0628\u0642\u06cc\u0647 \u062f\u0631 NP \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u06a9\u0631\u062f<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">\u0627\u0646\u0642\u0636\u0627<\/td>\n<td style=\"text-align: center;\">\u0645\u0633\u0627\u0626\u0644\u06cc \u06a9\u0647 \u062f\u0631 \u0632\u0645\u0627\u0646 \u062a\u0635\u0627\u0639\u062f\u06cc \u0642\u0627\u0628\u0644 \u062d\u0644 \u0647\u0633\u062a\u0646\u062f<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>\u0686\u0634\u0645 \u0627\u0646\u062f\u0627\u0632\u0647\u0627\u06cc \u0622\u06cc\u0646\u062f\u0647 \u0648 \u067e\u06cc\u0634\u0631\u0641\u062a \u0647\u0627\u06cc \u062a\u06a9\u0646\u0648\u0644\u0648\u0698\u06cc\u06a9\u06cc<\/h2>\n<p>\u0645\u062d\u0627\u0633\u0628\u0627\u062a \u06a9\u0648\u0627\u0646\u062a\u0648\u0645\u06cc \u0648 \u06cc\u0627\u062f\u06af\u06cc\u0631\u06cc \u0645\u0627\u0634\u06cc\u0646\u060c \u0622\u06cc\u0646\u062f\u0647 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0631\u0627 \u0634\u06a9\u0644 \u0645\u06cc \u062f\u0647\u0646\u062f. \u0645\u062d\u0627\u0633\u0628\u0627\u062a \u06a9\u0648\u0627\u0646\u062a\u0648\u0645\u06cc\u060c \u0628\u0627 \u067e\u062a\u0627\u0646\u0633\u06cc\u0644 \u062e\u0648\u062f \u0628\u0631\u0627\u06cc \u062d\u0644 \u0645\u0634\u06a9\u0644\u0627\u062a \u062e\u0627\u0635 \u0633\u0631\u06cc\u0639\u062a\u0631 \u0627\u0632 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631\u0647\u0627\u06cc \u06a9\u0644\u0627\u0633\u06cc\u06a9\u060c \u0628\u0627\u0639\u062b \u0627\u0631\u0632\u06cc\u0627\u0628\u06cc \u0645\u062c\u062f\u062f \u06a9\u0644\u0627\u0633 \u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0627\u06cc\u062c\u0627\u062f \u0634\u062f\u0647 \u0645\u06cc \u0634\u0648\u062f. \u0627\u0632 \u0633\u0648\u06cc \u062f\u06cc\u06af\u0631\u060c \u06cc\u0627\u062f\u06af\u06cc\u0631\u06cc \u0645\u0627\u0634\u06cc\u0646\u060c \u0627\u0646\u0648\u0627\u0639 \u062c\u062f\u06cc\u062f\u06cc \u0627\u0632 \u0633\u0648\u0627\u0644\u0627\u062a \u0645\u0631\u062a\u0628\u0637 \u0628\u0627 \u0645\u0646\u0627\u0628\u0639 \u0631\u0627 \u0627\u0631\u0627\u0626\u0647 \u0645\u06cc\u200c\u06a9\u0646\u062f \u06a9\u0647 \u0645\u0646\u062c\u0631 \u0628\u0647 \u062a\u0648\u0633\u0639\u0647 \u0645\u0639\u06cc\u0627\u0631\u0647\u0627 \u0648 \u06a9\u0644\u0627\u0633\u200c\u0647\u0627\u06cc \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u062c\u062f\u06cc\u062f \u0645\u06cc\u200c\u0634\u0648\u062f.<\/p>\n<h2>\u067e\u0631\u0648\u06a9\u0633\u06cc \u0647\u0627 \u0648 \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/h2>\n<p>\u062f\u0631 \u0632\u0645\u06cc\u0646\u0647 \u0633\u0631\u0648\u0631\u0647\u0627\u06cc \u067e\u0631\u0648\u06a9\u0633\u06cc\u060c \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u0628\u0647 \u0628\u0647\u06cc\u0646\u0647 \u0633\u0627\u0632\u06cc \u067e\u0631\u062f\u0627\u0632\u0634 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0647\u0627 \u06a9\u0645\u06a9 \u06a9\u0646\u062f. \u062f\u0631\u06a9 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u200c\u0647\u0627\u06cc \u0645\u0633\u06cc\u0631\u06cc\u0627\u0628\u06cc \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u0628\u0647 \u0637\u0631\u0627\u062d\u06cc \u06a9\u0627\u0631\u0622\u0645\u062f\u062a\u0631 \u0648 \u0645\u062a\u0639\u0627\u062f\u0644\u200c\u0633\u0627\u0632\u06cc \u0628\u0627\u0631 \u0628\u0647\u062a\u0631 \u0645\u0646\u062c\u0631 \u0634\u0648\u062f. \u0639\u0644\u0627\u0648\u0647 \u0628\u0631 \u0627\u06cc\u0646\u060c \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u0628\u0647 \u0637\u0631\u0627\u062d\u06cc \u0627\u0645\u0646\u06cc\u062a\u06cc \u0642\u0648\u06cc \u0628\u0631\u0627\u06cc \u067e\u0631\u0627\u06a9\u0633\u06cc \u0647\u0627 \u06a9\u0645\u06a9 \u06a9\u0646\u062f\u060c \u062c\u0627\u06cc\u06cc \u06a9\u0647 \u067e\u0631\u0648\u062a\u06a9\u0644 \u0647\u0627\u06cc \u0631\u0645\u0632\u0646\u06af\u0627\u0631\u06cc \u0646\u0642\u0634 \u062d\u06cc\u0627\u062a\u06cc \u062f\u0627\u0631\u0646\u062f.<\/p>\n<h2>\u0644\u06cc\u0646\u06a9 \u0647\u0627\u06cc \u0645\u0631\u0628\u0648\u0637\u0647<\/h2>\n<ol>\n<li><a href=\"https:\/\/plato.stanford.edu\/entries\/computational-complexity\/\" target=\"_new\" rel=\"noopener nofollow\">\u062f\u0627\u06cc\u0631\u0647 \u0627\u0644\u0645\u0639\u0627\u0631\u0641 \u0641\u0644\u0633\u0641\u0647 \u0627\u0633\u062a\u0646\u0641\u0648\u0631\u062f: \u0646\u0638\u0631\u06cc\u0647 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc<\/a><\/li>\n<li><a href=\"http:\/\/theory.cs.princeton.edu\/complexity\/book.pdf\" target=\"_new\" rel=\"noopener nofollow\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0645\u062d\u0627\u0633\u0628\u0627\u062a\u06cc: \u06cc\u06a9 \u0631\u0648\u06cc\u06a9\u0631\u062f \u0645\u062f\u0631\u0646 \u062a\u0648\u0633\u0637 \u0633\u0627\u0646\u062c\u06cc\u0641 \u0622\u0631\u0648\u0631\u0627 \u0648 \u0628\u0648\u0627\u0632 \u0628\u0627\u0631\u0627\u06a9<\/a><\/li>\n<li><a href=\"https:\/\/www.claymath.org\/millennium-problems\/p-vs-np-problem\" target=\"_new\" rel=\"noopener nofollow\">\u0635\u0641\u062d\u0647 P \u062f\u0631 \u0645\u0642\u0627\u0628\u0644 NP<\/a><\/li>\n<\/ol>","protected":false},"featured_media":467942,"menu_order":0,"template":"","meta":{"_acf_changed":false,"content-type":"","inline_featured_image":false,"footnotes":""},"class_list":["post-476352","wiki","type-wiki","status-publish","has-post-thumbnail","hentry"],"acf":{"faq_title":"Frequently Asked Questions about <mark>Computational Complexity Theory: Unfolding the Intricacies of Computational Power and Efficiency<\/mark>","faq_items":[{"question":"What is Computational Complexity Theory?","answer":"<p>Computational Complexity Theory is a branch of computer science that deals with the resources required to solve computational problems. It helps understand and assess the computational efficiency of algorithms and the limitations of computing.<\/p>"},{"question":"When and how did Computational Complexity Theory originate?","answer":"<p>Computational Complexity Theory originated as a distinct field in the 1950s and 1960s, but its principles were being developed from the start of theoretical computer science. The significant milestone was in 1965 when Juris Hartmanis and Richard Stearns proposed the time complexity classes P and EXP.<\/p>"},{"question":"What are the key features of Computational Complexity Theory?","answer":"<p>The key features of Computational Complexity Theory include problem classification, measurement of resource usage, determination of inherent problem difficulty, identification of computational limits, and discovery of computational equivalences.<\/p>"},{"question":"What types of complexity measures exist in Computational Complexity Theory?","answer":"<p>Several complexity measures exist, such as Time Complexity (computational time taken), Space Complexity (memory usage), Communication Complexity (required communication for distributed computation), Circuit Complexity (size of a boolean circuit that solves the problem), and Decision Tree Complexity (complexity of a problem in a binary decision-making model).<\/p>"},{"question":"How is Computational Complexity Theory used, and what are some related challenges?","answer":"<p>Computational Complexity Theory finds applications in algorithm design, cryptography, data structures, and more. The major challenge in the field is the lack of formal proofs for crucial questions like the P vs NP problem. Continuous development of proof techniques, computational models, and complexity classes help address these challenges.<\/p>"},{"question":"How does Computational Complexity Theory relate to future technologies like Quantum Computing and Machine Learning?","answer":"<p>Quantum computing, capable of solving certain problems faster than classical computers, prompts reevaluation of established complexity classes. Machine learning presents new types of resource-related questions, leading to the development of new complexity measures and classes.<\/p>"},{"question":"What is the relevance of Computational Complexity Theory to Proxy Servers?","answer":"<p>Understanding the computational complexity of routing algorithms can lead to more efficient design and better load balancing in proxy servers. Complexity theory can also assist in robust security design for proxies where cryptographic protocols play a vital role.<\/p>"}]},"_links":{"self":[{"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/wiki\/476352","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/wiki"}],"about":[{"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/types\/wiki"}],"version-history":[{"count":0,"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/wiki\/476352\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/media\/467942"}],"wp:attachment":[{"href":"https:\/\/oneproxy.pro\/ir\/wp-json\/wp\/v2\/media?parent=476352"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}