Вопросы с тегом «descriptive-complexity»

Расширение захвата SQL

По словам Иммермана , класс сложности, связанный с запросами SQL, - это в точности класс безопасных запросов в (запросы первого порядка плюс оператор подсчета): SQL захватывает безопасные запросы. (Другими словами, все запросы SQL имеют сложность в , и все проблемы в могут быть выражены как запрос...

Могут ли объединения быть распараллелены?

Предположим, мы хотим объединить два отношения в предикате. Это в NC? Я понимаю, что доказательство того, что он не находится в NC, будет равносильно доказательству того, что п≠ NСп≠NСP\not=NC , поэтому я бы принял доказательство того, что это открытая проблема, в качестве ответа. Меня интересует...