NP 문제입니까?

나는 최근에 NP과 P에 대한 기사를 읽었습니다. 주어진 단어의 조합을 찾는 문제는 NP 문제입니까? 예를 들어, 주어진 단어 anto, 결과는 anot, toan 등이 될 수 있습니다. 제가 알기 론, 우리가 다항식 시간에 문제에 대한 해를 확인할 수있을 때마다 그것은 NP 아래에 있다는 것을 의미합니다. 조합의 문제는 NP 아래에 있습니까?NP 문제입니까?

이것은 내가 NP와 P를 잘 이해했는지 알기위한 것입니다.

출처

2011-03-19 Ant' s

"주어진 문자 조합을 찾는 것"은 무엇을 의미합니까? – captncraig

주어진 단어의 죄송합니다 조합! –

NP는 의사 결정 문제로 구성되며 예 또는 대답이없는 문제로 NP에 있지 않습니다. 그러나이 문제는 "글자, 사전 및 그 사전 중 일부 단어의 모음이 주어지면 사전에는 있지만 그 안에는없는 글자의 아나그램이 있습니다"라고 다시 말하면서 결정 문제로 쉽게 만들 수 있습니다 우리가 지금까지 가지고있는 단어의 목록? "

이 문제는 다차원 시간 (따라서 비 결정적 다항식 시간)에서 확실히 풀릴 수 있습니다. 사전을 반복하면서 각 가능한 단어를 검사 할 수 있기 때문에 사전과 입력 단어의 크기로 시간 다항식을 취합니다. 그러나 예/아니오 질문을하지 않으므로 P 또는 NP 중 하나에 포함되지 않습니다.

희망이 도움이됩니다.

출처

2011-03-19 19:50:52 templatetypedef

OP가 실제 단어 (예 : 영어)에 대해 이야기하고 있는지 여부는 알 수 없지만, 그렇지 않은 경우 사전을 포기하고 단어 목록이 가능한 모든 분석기를 나타내는 지 여부를 묻는 것이 더 실제적 일 수 있습니다. 이 문제는 여전히 P ...이며 입력이 덜 필요합니다. 그냥 생각. – Patrick87

-1

AFAIK 문제에 대한 해결책이 없기 때문에 NP는 결정 문제입니다. 남아있는 것은 종종 폴리 노미 널 시간에 좋은 해답을 찾을 수있는 욕심 많은 알고리즘 또는 유전 알고리즘입니다. brute-force는 충실하지 못하며 최적의 솔루션을 찾지 못했습니다.

출처

2011-03-19 18:03:21 Bytemain

왜 downvote ......? – Bytemain

NP 문제입니까?

답변

관련 문제