P≠NP予想（P≠NPよそう、英: P is not NP）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。
P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。
理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、
2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。
Wikipedia「P≠NP予想」より
文字A、N、Pからなる文字列$S$が与えられる。
与えられた文字列$S$が、文字列PPAPからP = NPの置換を使って生成可能ならばYES、不可能ならばNOと出力せよ。
P = NPの置換とは、PをNPに置き換える、または、NPをPに置き換えることである。
例えば、文字列NPPAPは、PPAP先頭のPをNPに置換することで、生成可能である。
$1 \leq |S| \leq 1000$ -
$S$ はA、N、Pのみからなる。
1つの入力ファイルは複数のテストケースからなる。
入力ファイルの最初の1行目にはテストケースの個数$T$が記される$(1 \leq T \leq 50)$。
2行目以降には、$T$個のテストケースが記述されており、各テストケースは次の形式で表される。
$S$
各テストケースに対して、YESまたはNOを1行ずつ出力せよ。
3
NPPAP
PPNAP
NNPNNPAP
YES
NO
YES