Помощь      Поиск      Участники      Календарь      Новости
 Учебные Материалы      ВАЛтест     Фотогалерея Фотогалерея
 Правила форума      Виртуальные тренажеры      Мемуары


  Reply to this topicStart new topicStart Poll

> PSPACE-complete (Wikipedia)
Подписка на тему | Сообщить другу | Версия для печати
VAL
Дата 4.03.2021 13:52
Quote Post
Offline



Мэтр, проФАН любви... proFAN of love
*****

Профиль
Группа: Администраторы
Сообщений: 38049
Пользователь №: 1
Регистрация: 6.03.2004
PSPACE-complete (Wikipedia)
Источник: https://en.wikipedia.org/wiki/PSPACE-complete

QUOTE
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P and NP, but that is not known.[1] It is known that they lie outside of the class NC (a class of problems with highly efficient parallel algorithms), because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.


--------------------
www.valinfo.ru
Всегда... Always....
Quod licet jovi, non licet bovi!
PMEmail PosterUsers Website
Top
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Международный конгресс юмористов (в Питере) + Text mining | Следующая тема »

Topic Options Reply to this topicStart new topicStart Poll

 

Powered by Invision Power Board(U) v1.3 Final © 2003  IPS, Inc.
Установка, модификация и поддержка:
Barsum | 1px Design Group & Xac | OппаRU форум