88൐ཤ౷֖ब‫ݪࡄڠشٺ‬ȁల71‫ے‬Ȫ3135ȫ

௧ ࿴  ᖺ  ᭶㇦㞵᫬ࡢ㤿ሙ┠ᕝ࡟࠾ࡅࡿὥỈ࡟ࡘ࠸࡚              ⛅ ⏣኱Ꮫ⌮ᕤᏛ㒊⛅ⴥᾏᚿ⛅⏣኱Ꮫ኱Ꮫ㝔⌮ᕤᏛ◊✲⛉     ⮬ぢᑑᏕ⛅⏣኱Ꮫ኱Ꮫ㝔⌮ᕤᏛ◊✲⛉     㰻⸨᠇ᑑ⛅⏣኱Ꮫ኱Ꮫ㝔⌮ᕤᏛ◊✲⛉     Ώ㎶୍ஓ㸬ࡣࡌࡵ࡟ ⛅⏣┴࡛ࡣ௧࿴  ᖺ  ᭶࡟ࡼࡿグ㘓ⓗ࡞኱㞵࡟ࡼࡿὥỈ  ࡟ࡼࡾ㸪⛅⏣┴ෆ᭱኱ࡢ஧⣭Ἑᕝ࡛࠶ࡿ㤿ሙ┠ᕝ  ࡛Ἑᗋኚືࡀ㉳ࡇࡗࡓࠋὥỈ࡟ࡼࡿ⿕ᐖࢆῶࡽࡍࡓࡵ࡟Ἑᗋኚືࡢ≉ᛶࢆᢕᥱࡋ㸪⟶⌮ࡍࡿࡇ࡜ࡣ኱ษ࡛࠶ࡿ  ࠋᮏ◊✲࡛ࡣ㤿ሙ┠ᕝࢆᑐ㇟࡜ࡋ  ᖺ࠿ࡽ  ᖺࡲ࡛ࡢἙᗋኚື࡜⛅⏣┴࡟ࡼࡾஂಖほᡤ࡛ほࡉࢀࡓ  ᖺ࠿ࡽ  ᖺࡢỈ఩ኚື  㸪ᩘ್ィ⟬ࢆ⾜࠸௧࿴  ᖺ  ᭶ࡢ㇦㞵᫬࡟࠾ࡅࡿ㤿ሙ┠ᕝࡢỈ఩㸪ὶ㔞ࡀἙᗋኚືࡸὶ㏿࡟࡝ࡢࡼ࠺࡞ᙳ㡪ࢆ୚࠼ࡓ࠿࡟ࡘ࠸᳨࡚ウࡋࡓࠋ◊✲ᑐ㇟㤿ሙ┠ᕝࡣඵ㑻₲࡬ὶࢀࡿἙᕝ࡛࠶ࡿࠋᅗ  ࡟㤿ሙ┠ᕝࡢᴫせᅗࢆ♧ࡍࠋᅗ  ࡣほ㡿ᇦࡢ⛅⏣┴஬ᇛ┠⏫ᖹࣀୗᆅ༊࡟࠶ࡿ㤿ሙ┠ᕝࢆ♧ࡋࡓࡶࡢ࡛࠶ࡿࠋ㉥⥺ࡢ▮༳ࡀὶࢀࡢ᪉ྥࢆ♧ࡋ࡚࠾ࡾ㸪ୖὶഃ࠿ࡽࡣ 57. ࡛⥺ 㹼⥺  ࡜ࡋࡓࠋ ᖺ㹼 ᖺࡣගἼ㔞࡛㔞ࡋ㸪 ᖺ㔞ࡋࡓࠋஂಖほ⥺ ᡤ⥺ ⥺ 㤿ሙ┠ᕝ)//2:

Pඵ㑻†ୖὶ➃P

NP NPᅗ  ᑐ㇟㡿ᇦ㸬Ỉ఩ኚ໬ᅗ  ࡣほ㡿ᇦ࠿ࡽ NP ୗὶ࡟࠶ࡿஂಖほ ࡛࠶ࡾ㸪㉥⥺ࡣᡤࡢ  ᖺ࠿ࡽ  ᖺ࡟࠿ࡅ࡚ࡢỈ఩ࡢኚື㔞᫬ᮇࢆ⾲ࡋ࡚࠸ࡿࠋẖᖺ  ᭶࠿ࡽ  ᭶࡟࠿ࡅ࡚Ỉ఩ࡀ㧗ࡃ࡞ࡗ࡚࠾ࡾ㸪 'DPDJH FDXVHG E\ WKH )ORRG JHQHUDWHG WR +HDY\ 5DLQ DW $NLWD LQ -XO\  E\ .DLVKL $NLED㸪<RVKLWDND-LNHQ㸪1RULWRVKL6DLWRDQG.D]X\D:DWDQDEH89ỏ℃༴㝤Ỉ఩࡛࠶ࡿ P ࢆ㉸࠼࡚࠸ࡿᖺࡣ  ᖺ㸪 ᖺ㸪 ᖺ࡛࠶ࡿࠋ ᖺࡢỈ఩ࡣ PV ࡛࠶ࡾ㸪௚ࡢᖺ࡟ẚ࡭୍␒Ỉ఩ࡀ኱ࡁࡃ࡞ࡗ࡚࠸ࡿࠋ ᖺ ᖺᅗ ᖺ ᖺ ᖺ⥺ 㸪ᅗ  ࡀ⥺ 㸪ᅗ  ࡣ ᖺỈ఩ࡢኚື㸦ஂಖほᡤ㸧᩿㠃ᅗࡢኚ໬ᅗ 㸪ᅗ 㸪ᅗ  ࡣ  ᖺ㹼 ᖺࡢ᩿㠃ᅗ࡛࠶ࡿࠋᅗ  ࡀ⥺  ࡛࠶ࡿࠋᅗ  ࡢ  ᖺ࡜  ᖺࢆẚ㍑ࡍࡿ࡜ᕥᓊഃࡀ P ሁ✚ࡋ࡚࠸ࡿࠋ ᖺ࡜ ᖺࢆẚ㍑ࡍࡿ࡜ᕥᓊഃࡀ P ሁ✚㸪ྑᓊഃࡀ P ሁ✚ࡋ࡚࠸ࡿࠋᅗ  ࡢ  ᖺ࡜  ᖺࢆẚ㍑ࡍࡿ࡜ᕥᓊഃࡀ P ሁ✚ࡋ࡚࠸ࡿࠋ ᖺ࡜  ᖺࢆẚ㍑ࡍࡿ࡜ᕥᓊഃࡀ P ሁ✚㸪ྑᓊഃࡀ P ሁ✚ࡋ࡚࠸ࡿࠋᅗ  ࡢྑᓊഃࡀ  ᖺ࡜  ᖺࢆẚ㍑ࡍࡿ࡜ P ሁ✚ࡋ࡚࠸ࡿ HOHYDWLRQ Pᖺ࡜  ᖺࢆẚ㍑ࡍࡿ࡜ᕥᓊഃࡀ P Ὑᇼ㸪ྑᓊഃࡀ P ሁ✚ࡋ࡚࠸ࡿࠋ

HOHYDWLRQ Pᅗᅗ
GLVWDQFH P⥺  ᩿㠃ᅗ
GLVWDQFH P⥺  ᩿㠃ᅗ

HOHYDWLRQ P

8:ᅗ
GLVWDQFH P⥺  ᩿㠃ᅗᩘ್ィ⟬Ἑᗋኚືࡢゎᯒ࡟ࡣᖹ㠃  ḟඖィ⟬ᘧࢆ౑⏝ࡋࡓࠋ௨ୗࡢ  㹼  ࡀィ⟬ᘧ࡛࠶ࡿࠋ߲݄ ݀ሺ݄‫ݑ‬ሻ ߲ሺ݄‫ݒ‬ሻ൅൅ൌͲ߲‫ݐ‬݀‫ݔ‬߲‫ݕ‬͐͐ ߲ሺ‫݄ݑ‬ሻ ݀ሺ݄‫ݑ‬ଶ ሻ ߲ሺ݄‫ݒݑ‬ሻ݀‫ݐ ܪ‬௫൅൅ൌ െ݄݃െ ൅ ‫ܦ‬௫݀‫ݔ‬߲‫ݐ‬߲‫ݕ‬݀‫ߩ ݔ‬͐͐ ߲ሺ‫݄ݒ‬ሻ ݀ሺ݄‫ ݒ‬ଶ ሻ ߲ሺ݄‫ ݒ‬ଶሻ݀‫ݐ ܪ‬௬൅൅ൌ െ݄݃െ ൅ ‫ܦ‬௬߲‫ݐ‬݀‫ݔ‬߲‫ݕ‬݀‫ߩ ݕ‬͐͐ ‫ݐ‬௫ൌ ‫ܥ‬௙ ‫ݑ‬ඥ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶߩ͐͐ ‫ݐ‬௬ൌ ‫ܥ‬௙ ‫ݒ‬ඥ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶߩ͐͐ ‫ܥ‬௙ ൌଶ݃݊௠ଵ݄ଷ݊௠ ൌଵ݇௦଺͹Ǥ͸͸ඥ݃͐͐ ͐͐ ‫ܦ‬௫ ൌ݀݀‫ݑ‬݀‫ݑ‬݀൤ܸ௧ ݄ ൨ ൅൤ܸ௧ ݄ ൨݀‫ݔ‬݀‫ݔ‬݀‫ݕ‬݀‫ݕ‬‫ܦ‬௬ ൌ݀݀‫ݑ‬݀‫ݑ‬݀൤ܸ௧ ݄ ൨ ൅൤ܸ௧ ݄ ൨݀‫ݔ‬݀‫ݔ‬݀‫ݕ‬݀‫ݕ‬͐͐ ͐͐ ࡇࡇ࡟㸪K ࡣỈ῝㸪W ࡣ᫬㛫㸪X㸪Y ࡣ [㸪\ ᪉ྥࡢỈ῝ᖹᆒὶ㏿㸪J ࡣ㔜ຊຍ㏿ᗘ㸪+ ࡣỈ఩
W[㸪W\ ࡣ [㸪\ ᪉ྥࡢἙᗋࡏࢇ᩿ຊ㸪'[㸪'\ ࡣᣑᩓ㡯㸪&I ࡣἙᗋᦶ᧿ಀᩘ㸪QP ࡣ࣐ࢽࣥࢢࡢ⢒ᗘಀᩘࢆ♧ࡋ࡚࠸ࡿࠋᘧ  ࡀ㐃⥆ᘧ࡛࠶ࡾ㸪ᘧ   ࡀ㐠ື᪉⛬ᘧ࡛࠶ࡿࠋቃ⏺᮲௳ୖὶ➃ὶ㔞ࢆ  ᖺ  ᭶  ᪥࠿ࡽ  ᪥ࡲ࡛ࡢ  ᫬㛫࠶ࡓࡾࡢὶ㔞ኚ໬ࢆ౑⏝ࡋ㸪ᅗ  ࡟♧ࡋࡓࠋ ᪥ࡢ༗๓  ࠿ࡽỈ఩ࡀୖ᪼ࡋ㸪 ᫬㛫ᚋ࡟ὶ㔞ࡀࣆ࣮ࢡ࡟㐩ࡋ࡚࠾ࡾ㸪ࡑࡢ್ࡣPV ࡛࠶ࡗࡓࠋ91



GLVFKDUJH PVWLPH KRXUVᅗὶ㔞 ᖺ  ᭶  ᪥㹼 ᪥ ィ⟬᮲௳ィ⟬᮲௳ࢆ⾲  ࡟♧ࡋࡓࠋ᪤ ◊✲  ࢆཧ⪃࡟ࡋ࡚࣐ࢽࣥࢢࡢ⢒ᗘಀᩘࡣἙᗋࡣ 㸪ࡑࡢ௚ࢆ 㸪⢏ᚄࡣΰྜ⢏ᚄࢆ㑅ᢥࡋࡓࠋᮏ◊✲࡛ࡣ㸪஺᥮ᒙ࡜ሁ✚ᒙࡢ⢏ᗘศᕸࡢ୚࠼᪉࡜ࡋ࡚⢏ᚄຍ✚᭤⥺ࢆ౑⏝ࡋࡓࠋࡑࡢ⢏ᚄຍ✚᭤⥺ࡣᅗ  ࡟♧ࡋ࡚࠸ࡿࠋィ⟬᮲௳⪃៖ࡍࡿᒙΰྜ⢏ᚄἙᗋ࣐ࢽࣥࢢࡢ⢒ᗘಀᩘࡑࡢ௚᫬㛫ࢫࢸࢵࣉVィ⟬᱁Ꮚ㠀ṇ᪉᱁Ꮚὶ◁ࡢ✀㢮ᤲὶ◁࡜ᾋ㐟◁ᤲὶ◁࣋ࢡࢺࣝᘧΏ㑔ࡢᘧᾋ㐟◁ᾋୖ㔞ᘧᯈ಴࣭ᓊࡢᘧ஺᥮ᒙࡢཌࡉPሁ✚ᒙ୍ᒙࡢཌࡉ

PึᮇἙᗋ௨ୗࡢ඲⛣ືᒙཌ

P⪃៖ྍ⬟࡞ᒙཌWKURXJKWKHSHUFHQWDJH ⾲SDUWLFOH PPᅗ⢏ᚄຍ✚᭤⥺Ỉ῝㸪ὶ㏿㸪ᶆ㧗ኚ໬Ỉ῝㸪ὶ㏿㸪ᶆ㧗ኚ໬ࡢẚ㍑࡟ࡣ᪤ ◊✲  ࢆཧ⪃࡟ࡋࡓࠋᅗ  ࡣึᮇ࡜ࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡢỈ῝࡛࠶ࡿࠋึᮇࡣỈ῝ࡀ P㸪ࣆ࣮ࢡ᫬ࡢỈ῝ࡣ୰ᚰ⥺ࡢ࠶ࡓࡾࡀ P㸪ᕥᓊྑᓊഃࡀ P㸪 ᫬㛫ᚋࡢỈ῝ࡣ୰ᚰ⥺ࡢ࠶ࡓࡾࡀ P㸪ᕥᓊྑᓊഃࡀ P ࡛࠶ࡗࡓࠋᅗ  ࡣึᮇ࡜ࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡢὶ㏿࣋ࢡࢺ࡛ࣝ࠶ࡿࠋึᮇࡣὶ㏿࣋ࢡࢺࣝࡀᑠࡉࡃ㸪ࣆ࣮ࢡ᫬ࡣὶ㏿࣋ࢡࢺࣝࡀ኱ࡁࡃ㸪 ⥺  ࠿ࡽ⥺  ࡢ㛫ࡢ‴᭤㒊ࡢྑᓊഃ࡬ὶ㏿࣋ࢡࢺࣝࡀྥ࠸࡚࠸ࡓࠋ ᫬㛫ᚋࡣึᮇࡼࡾࡣὶ㏿࣋ࢡࢺࣝࡀ኱ࡁ࠿ࡗࡓࠋᅗ  ࡣࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡢᶆ㧗ኚ໬࡛࠶ࡿࠋ࡝ࡕࡽࡶ⥺  ࠿ࡽ⥺  ࡢ‴᭤㒊ࡢᶆ㧗ኚ໬ࡀ୍␒኱ࡁ࠸ࠋࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋ࡛ࡣ࠶ࡲࡾ㐪࠸ࡣぢࡽࢀ࡞࠿ࡗࡓࠋ ᫬㛫ᚋࡢὶ㏿࣋ࢡࢺࣝࡀᑠࡉ࠿ࡗࡓࡓࡵ㸪ሁ✚ࡸὙᇼࡀ࠶ࡲࡾ㉳ࡇࡽ࡞࠿ࡗࡓࡓࡵࡔ࡜⪃࠼ࡽࢀࡿࠋ

92

⥺⥺

⥺⥺⥺

⥺⥺⥺⥺SHDN

LQLWLDOᅗKRXUVỈ῝⥺⥺⥺⥺⥺⥺⥺

9HORFLW\ PV

9HORFLW\ PV⥺⥺

9HORFLW\ PVKRXUVSHDNLQLWLDOᅗ ὶ㏿࣋ࢡࢺࣝ⥺⥺⥺⥺⥺⥺⥺

SHDNLQLWLDO
ᅗ ⥺⥺KRXUVᶆ㧗ኚ໬ᩘ್ィ⟬࡟ࡼࡿ᩿㠃ᅗࡢኚ໬ࢆẚ㍑ࡋࡓࠋᅗ 㹼ᅗ  ࡣึᮇ㸪ࣆ࣮ࢡ᫬㸪 ᫬㛫ᚋࡢᩘ್ィ⟬ࡢ⤖ᯝ࡜㔞⤖ᯝࡢ᩿㠃ᅗࢆẚ㍑ࡋࡓࡶࡢ࡛࠶ࡿࠋᅗ  ࡣ⥺  ࡛࠶ࡿࠋᅗ  ࡣ⥺ 㸪ᅗ  ࡣ⥺ 㸪ᅗ  ࡣ㔞⤖ᯝ࡜ᩘ್ィ⟬࡛⤖ᯝࡀ␗࡞ࡗࡓࠋ 㔞⤖ᯝࡣึᮇ࡜ྠࡌP ௜㏆ࡢ㧗ࡉ࡛࠶ࡗࡓࡀ㸪ࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡣP ࡛࠶ࡾ㸪P ࡢ㐪࠸ࡀ࠶ࡗࡓࠋᅗ  ࡣࡶᩘ್ィ⟬ࡶᕥᓊࡀሁ✚ࡋ㸪ྑᓊࡀᾐ㣗ࡋ࡚࠸ࡓࡀ㸪㔞⤖ᯝࡣึᮇ࡜ẚ࡭࡚ P ሁ✚ࡋ㸪ࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡣ P ሁ✚ࡋ࡚࠾ࡾ㸪ሁ✚ࡢ㧗ࡉࡀ␗࡞ࡗ࡚࠸ࡓࠋྑᓊࡢᇼࡉࢀ࡚࠾ࡾ㸪ࣆ࣮ࢡ᫬࡜  ᫬㛫ᚋࡣ P Ὑᇼࡉࢀ࡚࠸ࡓࠋᅗ  ࡣᮇ࡜ẚ࡭ᕥᓊഃࡀὙᇼࡉࢀ࡚࠸ࡓࡀ㸪ࡓࠋྑᓊഃࡢ㔞⤖ᯝ㔞⤖ᯝࡣ P Ὑ㔞⤖ᯝࡶᩘ್ィ⟬ࡶึ㔞⤖ᯝࡣ P Ὑᇼࡉࢀ㸪ᩘ್ィ⟬ࡣ P Ὑᇼࡉࢀ࡚࠸㔞⤖ᯝࡣึᮇ࡜ẚ࡭ P Ὑᇼࡉࢀ࡚࠸ࡓࡀ㸪ᩘ್ィ⟬ࡢኚ໬ࡣ࡞࠿ࡗࡓࠋ㸪 ್HOHYDWLRQ P

LQLWLDOSHDNKRXUVPHDVXUHG
ᅗ GLVWDQFH P⥺  ᩘ್ィ⟬࡜㔞⤖ᯝࡢ᩿㠃93

HOHYDWLRQ P

LQLWLDOSHDNKRXUVPHDVXUHG

HOHYDWLRQ Pᅗ 

GLVWDQFH P⥺  ᩘ್ィ⟬࡜㔞⤖ᯝࡢ᩿㠃

LQLWLDOSHDNKRXUVPHDVXUHGᅗ GLVWDQFH P⥺  ᩘ್ィ⟬࡜㔞⤖ᯝࡢ᩿㠃㔞⤖ᯝ ᩿㠃㸬࠾ࢃࡾ࡟ᮏ◊✲࡛ࡣ௧࿴  ᖺ  ᭶ࡢ㤿ሙ┠ᕝࡢὥỈ࡟ࡘ࠸᳨࡚ウࡋࡓࠋ ᖺ㹼 ᖺࡢᶓ᩿ᅗࡢኚ໬ࡣ  ᖺ࡛ࡣ⥺  ࡣᕥᓊഃࡀ P ሁ✚㸪 ⥺  ࡢᕥᓊഃࡀ P ሁ✚㸪 ⥺  ࡣྑᓊഃࡀ Pሁ✚ࡋ࡚࠸ࡓࠋᩘ್ィ⟬࡜㔞⤖ᯝࡢẚ㍑࡛ࡣ㐣ཤࡢ㔞ࡋࡓ  ᖺ㛫ࡢἙᗋኚື࡜Ὑᇼ㸪ሁ✚ࡢ㧗ࡉࢆศᯒࡋ㸪ᩘ್ィ⟬ࡀ෌⌧࡛ࡁ࡚࠸ࡿ࠿ࢆ☜ㄆࡋࡓࠋ㔞⤖ᯝ࡜ᩘ್ィ⟬࡛ሁ✚㸪Ὑᇼࡢ㧗ࡉࡀ␗࡞ࡿࡇ࡜ࡀศ࠿ࡗࡓࠋㅰ㎡ᮏ◊✲ࢆ⾜࠺࡟࠶ࡓࡾ⛉Ꮫ◊✲㈝⿵ຓ㔠㸦+ ௦⾲㸸㢼㛫⪽㸧ࡢຓᡂࢆཷࡅࡓࠋࡇࡇ࡟グࡋ㸪ㅰពࢆ⾲ࡍࡿࠋཧ⪃ᩥ⊩ ⛅⏣┴⥲ົ㒊⥲ྜ㜵⅏ㄢ㸸⛅⏣┴㜵⅏࣏࣮ࢱࣝࢧ࢖ࢺ㸺KWWSVZZZERXVDLDNLWDMSSDJHV"DUWLF
OHBLG 㸼㸪㸦 ᖺ  ᭶  ᪥㜀ぴ㸧㸬 ⛅⏣┴㸸஧⣭Ἑᕝ㤿ሙ┠ᕝỈ⣔㸪㤿ሙ┠ᅪᇦἙᕝᩚഛィ⏬ኚ᭦KWWSVZZZSUHIDNLWDOJMSXSO
RDGVSXEOLFDUFKLYHBBVHLELBEDEDPHSGI !  ᖺ  ᭶  ᪥㜀ぴ 㸬 ᅜᅵ஺㏻┬㸸Ἑᕝࡢ⥔ᣢ⟶⌮࡟ࡘ࠸࡚KWWSVZZZPOLWJRMSULYHUVKLQQJLNDLBEORJVKDVHLVKLQND
VHQEXQNDNDLVKRXLLQNDLUMLJ\RXK\RXNDGDLNDLGDLNDLBVLU\RXSGI!㸦 ᖺ  ᭶  ᪥㜀ぴ㸧㸬 ⛅⏣┴ᘓタ㒊Ἑᕝ◁㜵ㄢ㸸⛅⏣┴Ἑᕝ◁㜵᝟ሗࢩࢫࢸ࣒㸪KWWSVNDVHQSUHIDNLWDOJMSSF!
㸦 ᖺ  ᭶  ᪥㜀ぴ㸧㸬 ᳜ᮌὯኴᮁ㸪Ώ㎶୍ஓ㸸ᖹᡂ  ᖺ  ᭶⛅⏣㇦㞵࡟࠾ࡅࡿ㤿ሙ┠ᕝὥỈࡢ෌⌧࡜ሐ㜵⿕⅏࡟ࡘ࠸࡚㸪ᮾ໭ᆅᇦ⅏ᐖ⛉Ꮫ◊✲㸪➨  ᕳ㸪SS㸪㸬 ୰ᕝ㐶㸪㇂ཱྀ㞙ஓ㸪Ώ㎶୍ஓ㸪㰻⸨᠇ᑑ㸸㤿ሙ┠ᕝ࡟࠾ࡅࡿ㖄┤᪉ྥࡢ⢏ᗘศᕸኚ໬࡜Ἑᗋኚືィ⟬࡟㛵ࡍࡿ᳨ウ㸪ᮾ໭ᆅᇦ⅏ᐖ⛉Ꮫ◊✲ ➨  ᕳ㸪SS㸪㸬