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

௝ ྎᖹ㔝༡㒊ࡢఅᅾά᩿ᒙࡢ㟈ᗘணࡢヨࡳ 㸨 ᮾ໭኱Ꮫ኱Ꮫ㝔⌮Ꮫ◊✲⛉ ᆅ㟈࣭ᄇⅆண▱◊✲ほࢭࣥࢱ࣮ ᒸ⏣▱ᕫᒾᡭ኱Ꮫ⌮ᕤᏛ㒊 ᒸ⏣┿௓㸬ࡣࡌࡵ࡟ ᒸ⏣┿௓࣭௚㸦㸧ࡣ ཯ᑕἲᆅ㟈᥈ᰝࡸ㔜ຊ᥈ᰝ࡟ࡼࡾ ௝ྎᖹ㔝༡㒊࡟࠾࠸࡚అᅾά᩿ᒙࡢᏑᅾࢆ☜ㄆࡋࡓࠋࡑࡢ㛗ࡉࡣ NP ࡜࡞ࡾ Ẽ㇟ᗇ࣐ࢢࢽࢳ࣮ࣗࢻ᥮⟬࡛  ࡜࡞ࡿࠋ㉮ྥࡣ࠾ࡼࡑ༡࡛すഴᩳࡀ⪃࠼ࡽࢀࡿࠋ୍᪉ ᖹ㔝ࡢ㌾ᙅᆅ┙ࡣᆅ㟈Ἴࡢቑᖜ⋡ࡀ኱ࡁ࠸ࡇ࡜࠿ࡽ ㌾ᙅᆅ┙ୗࡢ᩿ᒙ࣭ᆅ㟈ࡣࡑࡢつᶍ࡟ẚ࡭࡚ ᆅ⾲࡛ࡢ኱ࡁ࡞᣺ᖜ࣭㟈ᗘࢆࡶࡓࡽࡍࡇ࡜ࡀ᝿ᐃࡉࢀࡿࠋᮏ◊✲࡛ࡣ అᅾά᩿ᒙࡢ㟈ᗘணࡢ౛࡜ࡋ࡚ ᒸ⏣┿௓࣭௚㸦㸧ࡢ௝ྎᖹ㔝༡㒊ࡢఅᅾά᩿ᒙ࡟ࡘ࠸࡚ 㟈ᗘணࢆヨࡳࡓࠋ㸬᪉ἲ ᒸ⏣┿௓࣭௚㸦㸧ࡢ᝿ᐃ᩿ᒙ࡟ᚑ࠺ࡼ࠺࡟௝ྎᖹ㔝༡㒊ୗ࡟అᅾ᩿ᒙࢆタᐃࡋࡓࠋ᩿ᒙ㛗ࡣ NP ࡜ࡋࡓࠋᡭ⥆ࡁࡣ ࠕ⡆౽ἲࠖ࡟ᚑࡗࡓࠋ⡆౽ἲ㸦౛࠼ࡤ 㤶ᕝ 㸧࡛ࡣ㸪㸯㸧᩿ᒙ㛗ࢆᇶᮏࡢ್࡜ࡋ㸪ࡇࢀࡲ࡛Ⓨ⏕ࡋࡓ኱つᶍᆅ㟈࡟࠾ࡅࡿ᩿ᒙ㛗࡜つᶍ㸦࣐ࢢࢽࢳ࣮ࣗࢻ㸧࡜ࡢᖹᆒⓗ࡞㛵ಀ࠿ࡽ㸪࣐ࢢࢽࢳ࣮ࣗࢻࡸ᩿ᒙࡢᖜࡸ῝ᗘ࡜࠸ࡗࡓࣃ࣓࣮ࣛࢱࢆồࡵࡿࠋ㸰㸧㊥㞳ῶ⾶ᘧ࡜࿧ࡤࢀࡿ㟈※㊥㞳࡜ᆅ㟈ື࡜ࡢ㛵ಀᘧࢆඖ࡟㸪ᇶ┙࡟࠾ࡅࡿᆅ㟈ືࡢ᭱኱㏿ᗘࢆồࡵࡿࠋ㸱㸧ᇶ┙࡟࠾ࡅࡿᆅ㟈ື࡟㸪ᚤᆅᙧ༊ศ࠿ࡽ᥎ᐃࡉࢀࡿᆅ㟈ືࡢቑᖜ⋡ࢆ࠿ࡅࡿࡇ࡜࡛ྛᆅⅬࡢᆅ⾲࡛ࡢ᭱኱㏿ᗘࢆồࡵ㸪᭱኱㏿ᗘ࠿ࡽ㟈ᗘ࡟᥮⟬ࡍࡿ㸪࡜࠸࠺ᡭ㡰ࢆ࡜ࡿࠋࡇࡢ᪉ἲ࡛ࡣ㸪᩿ᒙ࡛ࡢࡍ࡭ࡾࡸᆅୗᵓ㐀ࡢ୙ᆒ㉁ᛶ࡞࡝ヲ⣽࡞᝟ሗࡣ⪃៖ࡉࢀ࡞࠸ࡀ㸪⡆᫆࡞ᆅ㟈ື࣭㟈ᗘࡢ᥎ᐃ᪉ἲ࡜ࡋ࡚㸪඲ᅜࡢά᩿ᒙࡢ㟈ᗘணྛ ࣃ ࣛ ࣓ ࣮ ࢱ ࡣ ࠕ ඲ ᅜ ᆅ 㟈 ື ண࡟⏝࠸ࡽࢀ࡚࠸ࡿࠋᆅ ᅗ ᢏ ⾡ ሗ ࿌ ᭩

KWWSVMLVKLQJRMSPDLQFKRXVDB\RVRNXFKL]XJBPRGHOSGI ࠖ࡟ࡼࡾタᐃࡋࡓࠋ᩿ᒙ㛗 NP ࡣ0Z  ࡜᥮⟬ࡉࢀࡓࠋ㏆ഐࡢά᩿ᒙ࡛࠶ࡿ཮ⴥ᩿ᒙᖏ࡟࠾ࡅࡿタᐃ࡜ྠࡌࡃ ᒸ⏣▱ᕫ࣭௚㸦㸧ࡢ㟈※ศᕸ࡞࡝ࡶཧ⪃࡟ ᆅ㟈Ⓨ⏕ᒙࡢୗ㝈ࡣ NP ୖ㝈ࡣ NP ࡜௬ᐃࡋࡓࠋഴᩳゅࡣ㏫᩿ᒙࡢᖹᆒⓗ࡞್࡜ࡋ࡚  ᗘ࡜௬ᐃࡋࡓࠋࠕ඲ᅜᆅ㟈ືணᆅᅗ ᢏ⾡ሗ࿌᭩ࠖ࡟ࡼࡾ㸪᩿ᒙᖜࡣ NP ࡜ࡋࡓࠋ㜵⅏⛉◊ࡼࡾබ㛤ࡉࢀ࡚࠸ࡿࠕ㊥㞳ῶ⾶ᘧ࡟ࡼࡿᆅ㟈ືணࢶ࣮ࣝ㸦ඛྡ࣭⸨ཎ㸧ࠖࢆ౑⏝ࡋࡓࠋ㸬㸬 ⤖ᯝᅗ㸯࡟ᚤᆅᙧ༊ศࢆ♧ࡍࠋᅗ㸰࡟᝿ᐃࡉࢀࡿ㟈ᗘศᕸᅗࢆ♧ࡍࠋ㟈ᗘ㸴ᙅࢆ㉸࠼ࡿᆅᇦࡣ௝ྎᕷ௜㏆࠿ࡽ⚟ᓥ┴༡┦㤿ᕷ௜㏆ࡲ࡛༡໭࡟⣙ NP ᮾす࡟ᗈ࠸࡜ࡇࢁ࡛⣙ NP ࡜࡞ࡗࡓࠋ௝ྎᖹ㔝༡㒊ࡸ᩿ᒙࡼࡾすࡢᐑᇛ┴ゅ⏣ᕷ௜㏆ࡢ┅ᆅ࡛ࡣ㟈ᗘ  ᙉ௨ୖࡀ᥎ᐃࡉࢀࡓࠋ᩿ᒙࡢ
$QDWWHPSWWRSUHGLFWVHLVPLFLQWHQVLW\E\WKHEOLQGDFWLYHIDXOWEHQHDWKWKHVRXWKHUQ6HQGDLSODLQE\7RPRPL
2NDGDDQG6KLQVXNH2NDGD43ᆅ⾲ࢺ࣮ࣞࢫ࡜すഃࡢᒣᆅቃ⏺ࡢ㛫࡟ࡣᖏ≧ࡢ㟈ᗘ㸵⛬ᗘࡢ㡿ᇦࡶ☜ㄆࡉࢀࡓࠋᅗ ௝ྎᖹ㔝࿘㎶ࡢᚤᆅᙧ༊ศᅗ  ௝ྎᖹ㔝༡㒊ࡢఅᅾ᩿ᒙ࡟ࡼࡿ㟈ᗘศᕸ44㸬 ㆟ㄽ㸬ᮏ◊✲࡟ࡼࡿ㟈ᗘศᕸ࡟ࡘ࠸࡚࿘㎶ࡢ௚ࡢ᩿ᒙࡢ㟈ᗘண࡜ẚ㍑ࡋࡓ㸦ᅗ㸱㸧ࠋ௝ྎᖹ㔝༡㒊ࡢఅᅾ᩿ᒙࡢ 0Z ࡣ  ࡛ ᝿ᐃ᩿ᒙ㛗ࡣ NP ࡛࠶ࡿࠋ㛗⏫࣭฼ᗓ᩿ᒙࡸ཮ⴥ᩿ᒙࡣ 0Z࡛᝿ᐃ᩿ᒙ㛗ࡣ NP ࡛࠶ࡿࠋ௝ྎᖹ㔝༡㒊ࡢఅᅾ᩿ᒙࡣࡑࢀࡽ㸰ࡘࡢ᩿ᒙ࡜ẚ࡭ࡿ࡜㟈ᗘ㸴ᙅ௨ୖࡢ⠊ᅖࡣ⊃࠸ࡶࡢࡢ ᩿ᒙࡢᆅ⾲ࢺ࣮ࣞࢫ࡜すഃࡢᒣᆅቃ⏺ࡢ㛫࡟ぢࡽࢀࡿᖏ≧ࡢ㟈ᗘ㸵⛬ᗘࡢ㡿ᇦࡣ௚ࡢ㸰ࡘࡢ᩿ᒙࡼࡾࡶ㢧ⴭ࡟☜ㄆ࡛ࡁࡿࠋᅗ㸱 ᕥ࠿ࡽࠕ㛗⏫̿฼ᗓ᩿ᒙࠖࠕ௝ྎᖹ㔝༡㒊ࡢఅᅾ᩿ᒙࠖࠕ཮ⴥ᩿ᒙࠖ࡟ࡼࡿ㟈ᗘศᕸᅗࠋᮏ◊✲࡛௬ᐃࡋࡓࣃ࣓࣮ࣛࢱࡣ㸪୙☜ᐃᛶࡀ኱ࡁ࠸ࡓࡵ㸪௬ᐃࡢ⠊ᅖ࡟ࡼࡿ㟈ᗘศᕸࡢ⠊ᅖࢆ᳨ウࡋࡓࠋ୍౛࡜ࡋ࡚ ഴᩳゅࢆኚ࠼ࡓሙྜࡢ㟈ᗘศᕸࢆ☜ㄆࡋࡓ㸦ᅗ㸲㸧ࠋ᩿ᒙࡢᆅ⾲ࢺ࣮ࣞࢫ࡜すഃࡢᒣᆅቃ⏺ࡢ㛫࡟ぢࡽࢀࡿᖏ≧ࡢ㟈ᗘ㸵⛬ᗘࡢ㡿ᇦࡣഴᩳ  ᗘ࡛ࡣ㢧ⴭ࡛ࡣ࡞࠸ࡀ ഴᩳࡀ኱ࡁࡃ࡞ࡿ࡯࡝ ࡼࡾ㢧ⴭ࡜࡞ࡿࠋᅗ㸲㸬ഴᩳゅࢆኚ࠼ࡓሙྜࡢ㟈ᗘศᕸࠋᕥ࠿ࡽ  ᗘ ᗘ ᗘ࡜ࡋࡓሙྜࢆ♧ࡍࠋ

45ࡉࡽ࡟᩿ᒙࡢ᭱ࡶὸ࠸⁥ࡾ㡿ᇦࡢ῝ᗘࢆኚ࠼ࡓሙྜࡢ㟈ᗘศᕸࢆ☜ㄆࡋࡓ㸦ᅗ㸳㸧ࠋ᩿ᒙࡢᆅ
⾲ࢺ࣮ࣞࢫ࡜すഃࡢᒣᆅቃ⏺ࡢ㛫࡟ぢࡽࢀࡿᖏ≧ࡢ㟈ᗘ㸵⛬ᗘࡢ㡿ᇦࡣ㸪᭱ࡶὸ࠸⁥ࡾ㡿ᇦࡢ῝ᗘࡀࡼࡾὸࡃ࡞ࡿ࡯࡝ࡼࡾ㢧ⴭ࡜࡞ࡿࠋ
ᅗࠋ᩿ᒙࡢ᭱ࡶὸ࠸⁥ࡾ㡿ᇦࡢ῝ᗘࢆኚ࠼ࡓሙྜࡢ㟈ᗘศᕸࠋᕥ࠿ࡽ NP NP NP ࡜ࡋࡓሙྜࢆ♧ࡍࠋ㸬 ࡲ࡜ࡵ㸬㟈ᗘ  ᙅࢆ㉸࠼ࡿᆅᇦࡣ௝ྎᕷ௜㏆࠿ࡽ⚟ᓥ┴༡┦㤿ᕷ௜㏆ࡲ࡛༡໭࡟⣙ ࡜ࡇࢁ࡛⣙  ᮾす࡟ᗈ࠸

࡜࡞ࡾ ௝ྎᖹ㔝༡㒊ࡸ᩿ᒙࡼࡾすࡢᐑᇛ┴ゅ⏣ᕷ௜㏆ࡢ┅ᆅ࡛ࡣ㟈ᗘ  ᙉ௨ୖࡀ᩿ᒙᆅ⾲ࢺ࣮ࣞࢫ࡜すഃࡢᒣᆅቃ⏺ࡢ㛫࡟ࡣᖏ≧ࡢ㟈ᗘ⛬ᗘࡢ㡿ᇦࡶ☜ㄆࡉࢀࡓࠋࡇࡢࡼ࠺࡞㟈ᗘศᕸࡣ௬ᐃ࡟౫Ꮡࡋ࡚࠸ࡿࠋ⌧≧࡛ࡣ୙☜ᐇᛶࡀ኱ࡁࡃࡼࡾṇ☜࡞᥎ᐃ࣭࠶ࡿ࠸ࡣ᥎ᐃࡢᖜࡢ☜ㄆࡢࡓࡵ࡟ࡣ᩿ᒙࡢഴᩳゅࡸࡍ࡭ࡾࡀⓎ⏕ࡍࡿ῝ࡉୖ㝈࣭ୗ㝈ࡢ᥎ᐃࡸ᥎ᐃ⠊ᅖࡢぢ✚ࡀᚲせ࡛࠶ࡿࠋ࡞࠾㸪ࠕ඲ᅜᆅ㟈ືணᆅᅗ ᢏ⾡ሗ࿌᭩ࠖ࡟ᚑ࠸㸪௒ᅇࡣ㸪᩿ᒙࡢᖜࢆ NP ࡜ࡋࡓࡀࡇࡢᆅᇦࡢᆅ㟈Ⓨ⏕ᒙࡢཌࡉ࡜᩿ᒙࡢഴᩳゅ࠿ࡽࡣࡼࡾ኱ࡁ࡞ᖜࡀᮇᚅࡉࢀࡿࡓࡵ ᩿ᒙᖜ࡟ࡘ࠸࡚ᮏ᩿ᒙ࡟㐺ࡋࡓ᥎ᐃ್࣭タᐃ್ࢆ⏝࠸ࡿࡇ࡜ࡶ⪃࠼ࡽࢀࡿࠋ ࡉࡽ࡟ࠊ௒ᚋ㸪ᚤᆅᙧ༊ศࡸࢧ࢖ࢺቑᖜ≉ᛶ࡟ࡘ࠸࡚ࡣࠊࡼࡾ᭱᪂ࡢࡶࡢࢆά⏝ࡋࠊࡼࡾ㧗ศゎ⬟࡛ಙ㢗ᛶࡢ㧗࠸᥎ᐃࢆ⾜࠺ணᐃ࡛࠶ࡿࠋࡲࡓᮏ᩿ᒙࡢάື≉ᛶ࡟ࡘ࠸࡚ࡣࠊ࿘ᅖࡢά᩿ᒙ㸪≉࡟㸪୍㒊୪⾜ࡋ㏆ഐࡢά᩿ᒙ࡛࠶ࡿ཮ⴥ᩿ᒙᖏ࡜ࡢ㛵ಀ㸦౛࠼ࡤ㸪బ⸨࣭௚㸪㸧࡟ࡘ࠸࡚ࡶ᳨ウࡍࡿᚲせࡀ࠶ࡿࠋ
ㅰ ㎡ᮏ◊✲ࡣ㸪ࠕ㊥㞳ῶ⾶ᘧ࡟ࡼࡿᆅ㟈ືணࢶ࣮ࣝ ඛྡ࣭⸨ཎ㸪 ࠖࢆ౑⏝ࡋࡲࡋࡓࠋ ⚟ᓥὒẶ࣭୰ཎᜏẶࡢࡈຓゝ㸪ᕷ౗㞞ၨẶ࣭㧘ᮌᾴኴẶࡢࡈ༠ຊ࡟ឤㅰ࠸ࡓࡋࡲࡍࠋᮏ◊✲ࡣᩥ㒊⛉

46Ꮫ┬࡟ࡼࡿࠕ⅏ᐖࡢ㍍ῶ࡟㈉⊩ࡍࡿࡓࡵࡢᆅ㟈ⅆᒣほ◊✲ィ⏬ࠖࡢᨭ᥼ࢆཷࡅࡲࡋࡓࠋ ཧ ⪃ᩥ⊩ᒸ⏣ ┿௓࣭௒Ἠ ಇᩥ࣭ᴘཎ ிᏊ࣭㉺ᚋ ᬛ㞝࣭ᡞ⏣ ⱱ࣭ᯇཎ ⏤࿴࣭୕㍯ ᩔᚿ࣭ఫ⏣ 㐩ဢ ཯ᑕἲᆅ㟈᥈ᰝ࠾ࡼࡧ㔜ຊ᥈ᰝ࠿ࡽ᫂ࡽ࠿࡟࡞ࡗࡓ௝ྎᖹ㔝༡㒊ࡢఅᅾά᩿ᒙ ᆅ㟈➨ ㍴GRL]LVLQᒸ⏣┿௓࣭㉺㇂ ಙ࣭⏣୰⨾ဏ࣭ᖹฟ⿱༤࣭ᒸ⏣▱ᕫ  㔜ຊ᥈ᰝ࡟ࡼࡿ௝ྎᖹ㔝༡㒊ࡢఅᅾά᩿ᒙ༡➃㒊ࡢ㐃⥆ᛶ ᮾ໭ᆅᇦ⅏ᐖ⛉Ꮫ◊✲㞟఍ᒸ⏣┿௓࣭㉺㇂ಙ࣭ఫ⏣㐩ဢ࣭᪂἟ᚭ☻࣭⏣୰⨾ဏ࣭ᖹฟ⿱༤࣭ᒸ⏣▱ᕫ ᆅୗᵓ㐀᥈ᰝ࠿ࡽ᫂ࡽ࠿࡟࡞ࡗࡓ௝ྎᖹ㔝༡㒊ࡢఅᅾά᩿ᒙ ᮾ໭ᆅᇦ⅏ᐖ⛉Ꮫ◊✲㞟఍ᒸ⏣▱ᕫ࣭୰ᒣ㈗ྐ࣭ᖹཎ ⪽࣭❧ᒾ࿴ஓ࣭ᇼෆⱱᮌ࣭ ຾ಛ ၨ࣭኱ᅬ┿Ꮚ࣭ᑠⳢṇ⿱࣭๓⏣ᣅே࣭ᒣ୰ెᏊ࣭∦ᑿ ᾈ࣭ᯇᓥ ೺࣭ඵᮌཎᐶ࣭ ᖺᮾ໭ᆅ᪉ኴᖹὒἈᆅ㟈⥭ᛴほ࣮ࣉ ᮾ໭ᆅ᪉୰༡㒊࡟࠾ࡅࡿ⮫᫬ᆅ㟈ほࢢࣝ ᮾ໭ᆅᇦ⅏ᐖ⛉Ꮫ◊✲KWWSQGVWRKRNXLQDUHQDQHMSQGVMRXUQDOYROXPHSGI㤶ᕝᩗ⏕ ᙉ㟈ືணᡭἲࡢᴫせ ᪥ᮏᆅ㟈Ꮫ఍ࢽ࣮ࣗࢫࣞࢱ࣮1/BB1/BBబ⸨ẚ࿅ᚿ࣭㉺㇂ ಙ࣭▼ᒣ㐩ஓ㸪㸪཮ⴥ᩿ᒙ࡟࠾ࡅࡿ㧗ศゎ⬟཯ᑕἲᆅ㟈᥈ᰝ࣭㔜ຊ᥈ᰝ㸪㸪ᮾ໭ᆅ᪉ኴᖹὒἈ࡛Ⓨ⏕ࡍࡿᆅ㟈࣭ὠἼࡢㄪᰝほ ᖹᡂ㸰㸲ᖺᗘ ᡂᯝሗ࿌᭩ ᩥ㒊⛉Ꮫ ┬ ◊ ✲ 㛤 Ⓨ ᒁ ࣭ ᅜ ❧ ኱ Ꮫ ἲ ே ᮾ ி ኱ Ꮫ ᆅ 㟈 ◊ ✲ ᡤ  
KWWSVZZZMLVKLQJRMSPDLQFKRXVDNHQN\XXWRKRNXBWVXQDPLK5HSRUWB&KDSBBSGI㸬ඛྡ㔜ᶞ࣭⸨ཎᗈ⾜   ᆅ㟈ືணᆅᅗసᡂࢶ࣮ࣝࡢ㛤Ⓨ 㜵⅏⛉Ꮫᢏ⾡◊✲ᡤ◊✲㈨ᩱ

➨  ྕKWWSVGLORSDFERVDLJRMSSXEOLFDWLRQQLHGBWHFKBQRWHSGIQSGI