Кто-нибудь знает, что означает P (Σ *)? также известный как SΣ.Что означает P (Σ *) в теории сложности?
Я не знаю, как начать поиск P (Σ *), не зная, что это такое.
В этом контексте я считаю, что P относится к power set, множеству всех подмножеств множества. В этом случае P (Σ *) означает «комплект мощности Σ *». Это набор всех языков над Σ, так как он содержит все наборы строк из символов в Σ.
Надеюсь, это поможет!
Пожалуйста, исправьте меня, если я ошибаюсь. Если Σ = {a, b}. Тогда Σ * - множество всей длины конечной длины над Σ. Итак, Σ * = {a, b, ab, aa, bb, aabb, aab, ....} должны быть бесконечными. Что это за власть? .. Все еще немного запутался. – geasssos
@ geasssos- Это правильно. Бесконечные множества могут иметь силовые множества, как конечные множества; это просто бесконечно велико. – templatetypedef
@geasssos Силовой набор '{a, b, ab, aa, bb, aabb, aab, ....}' является '{{}, {a}, {b}, {a, b}, { ab}, {a, ab}, {b, ab}, {a, b, ab} ...} ' – Alexander
P обычно используется для обозначения полиномиального времени, но я никогда не видел его с фактическим аргументом. Возможно, вам повезло узнать об этом на [cstheory.se]. –
@ JB.- cstheory больше подходит для вопросов CS на уровне исследований. Вероятно, это лучше подходит для cs.stackexchange.com, что является хорошим местом для того, чтобы задавать более теоретические вопросы CS, которые не находятся на уровне исследований. – templatetypedef