2D⣖ఀ༙ᓥ኱Ỉᐖ ኱⏿™࡟࠾ࡅࡿᆅ㉁࣭Ỉᩥㄪᰝ࡜ࡑࡢ⪃ᐹዉⰋ┴┴ᅵ࣐ࢿࢪ࣓ࣥࢺ㒊῝ᒙᔂቯᑐ⟇ᐊ       Ᏻ஭ᗈஅዉⰋ┴஬ᲄᅵᮌ஦ົᡤ           ᖹฟ⩏༤࣭ຬᕝ㑥ᾈᅜ㝿⯟ᴗᰴᘧ఍♫        ‫ۑ‬ୗᒣ୍ஓ࣭኱⚄᫛ᚨ࣭ᓥ⏣ᚭᰴᘧ఍♫ዉⰋᆅ㉁                 ྂᕷ࿘஧㸯㸬ࡣࡌࡵ࡟ዉⰋ┴ྜྷ㔝㒆༑ὠᕝᮧす༡㒊࡟఩⨨ࡍࡿ኱⏿™ࡣࠊ᫂἞  ᖺ  ᭶ࡢ᫂἞༑ὠᕝ኱Ỉᐖ᫬࡟ᙜヱ῱ὶࡢᕥᓊഃ࡟࡚኱ᔂቯࡀⓎ⏕ࡋࠊᔂቯᅵ◁࡟ࡼࡿἙ㐨㛢ሰ࡜ࡑࡢᙳ㡪࡟ࡼࡗ࡚ᙧᡂࡉࢀࡓୖὶഃࡢሖࡁṆࡵụࡀ⣙  ᖺ⤒㐣ࡋࡓ⌧ᅾ࡛ࡶ၏୍ṧࡗ࡚࠸ࡿ῱ὶ࡛࠶ࡿࠋᖹᡂ  ᖺ  ᭶ࡢ⣖ఀ༙ᓥ኱Ỉᐖ᫬࡟Ἑ㐨㛢ሰ㒊ࡀ኱ࡁࡃ౵㣗࣭ᔂቯࡋ࡚ᅵ▼ὶࡀⓎ⏕ࡋࠊ୍⯡ᅜ㐨  ྕࡀ㏻⾜୙⬟࡟࡞ࡿ࡜࡜ࡶ࡟Ꮩ❧㞟ⴠࡀᙧᡂࡉࢀࡿ➼ࡢከ኱࡞⿕ᐖࡀⓎ⏕ࡋࡓࠋ⌧ᅾࡶ᫂἞࡟ᙧᡂࡉࢀࡓἙ㐨㛢ሰ㒊ࡢ኱㒊ศࡣṧᏑࡋ࡚࠾ࡾࠊୗὶഃ࡛ࡣ⥭ᛴᑐ⟇࡜ࡋ࡚࠼ࢇሐࡢᕤ஦ࡀ㐍ࡵࡽࢀ࡚࠸ࡿࠋࡇࡇ࡛ࡣࠊἙ㐨㛢ሰ㒊࡟࠾ࡅࡿᆅ㉁࣭Ỉᩥㄪᰝࢆ⾜࠸ࠊἙ㐨㛢ሰ㒊ࡢᏳᐃᛶࡸ௒ᚋࡢᑐᛂ᪉㔪➼࡟ࡘ࠸᳨࡚ウࡋࡓ⤖ᯝࢆሗ࿌ࡍࡿࠋ⋢ᇉෆ᩿ᒙ㻌ᇶ┙䛾ᆅ㉁ᵓ㐀䠗ὶ䜜┙㸰㸬ὶᇦᴫせN䠄䠍䠅ᆅᙧᴫせ㻌ᙜヱ῱ὶࡣ᪂ᐑᕝỈ⣔すᕝࡢᕥᨭᕝ࡛ὶᇦ
኱ᔂቯ㊧㻌㠃✚ NP ࡛࠶ࡿࠋᅗ  ࡣᙜヱ῱ὶࡢᴫἣᅗࢆ♧ࡋࡓࡶࡢ࡛࠶ࡿࠋᅗ࡟♧ࡍࡼ࠺࡟ᕥᓊᩳ㠃࡟࠾ࡅࡿ኱つᶍᔂቯ࡟ࡼࡿἙ㐨㛢ሰࡀⓎ⏕ࡋࠊୖὶഃ࡟኱⏿Ἑ㐨㛢ሰ㒊㻌™࡜࿧ࡤࢀࡿࡓࡵụࡀṧᏑࡋ࡚࠸ࡿࠋ኱⏿™ụ㻌኱つᶍᔂቯࡣࠊᖜ⣙ Pࠊ㛗ࡉ⣙ Pࠊ㧗ࡉ⣙ 㹼P ࡢつᶍࢆ᭷ࡋࠊᔂቯ᫬ࡢ⛣ືᅵすᕝ㻌౵㣗ᓴ㻌ሢࡣᑐᓊࡲ࡛ศᕸࡋ࡚Ἑ㐨ࢆ㛢ሰࡋࠊᩳ㠃ෆ‪Ỉ⟠ᡤ㻌ࡣ㉳అ࡟ᐩࡴ⦆ഴᩳᆅ࡜࡞ࡗ࡚࠸ࡿࠋ
䠄䠎䠅ᆅ㉁ᴫせ㻌
ᆅ㉁ࡣ୰⏕௦ⓑள⣖ᅄ୓༑ᖏ᪥㧗ᕝᒙ⩌ࡢᅗ 㻝䠊኱⏿™㻌 ᴫἣᅗ㻌㡫ᒾඃໃࡢ◁ᒾ㡫ᒾ஫ࡀศᕸࡋ࡚࠸ࡿࠋᆅ㉁ᵓ㐀ࡣ໭ᮾ༡す᪉ྥࡢ㉮ྥࠊ໭す࡟ഴᩳࡍࡿࡶࡢࡀ༟㉺ࡋ࡚࠾ࡾࠊ኱つᶍᔂቯࡣὶࢀ┙࡟㉳ᅉࡋ࡚Ⓨ⏕ࡋࡓࡶࡢ࡜᥎ᐹࡉࢀࡿࠋࡲࡓࠊᔂቯᆅෆࡣ⋢ᇉෆ᩿ᒙ࡜࿧ࡤࢀࡿ᥎ᐃ᩿ᒙࡀ㏻㐣ࡍࡿࡇ࡜ࡀሗ࿌ࡉࢀ࡚࠸ࡿ  ࠋᙜヱᆅෆࡢ࣮࣎ࣜࣥࢢㄪᰝࡢ⤖ᯝ࠿ࡽࠊἙ㐨㛢ሰ㒊ࡣᒾሢΰࡌࡾࡢ◁♟ࡀ᭱኱ 㹼P ࡢᒙཌ࡛ศᕸࡍࡿࡇ࡜ࡀࢃ࠿ࡗࡓࠋ
⣖ఀ༙ᓥ኱Ỉᐖ࡟ࡼࡗ࡚Ἑ㐨㛢ሰ㒊ࡀ㛗ࡉ Pࠊ㧗ࡉ᭱኱⣙ P㸪ᖜ᭱኱P ࡟ࢃࡓࡗ࡚኱つᶍ࡞౵㣗࣭ᔂቯࡀⓎ⏕ࡋࡓࠋ⌧ᅾࡣୗὶࡢすᕝ࡟࠿ࡅ࡚㠀ᖖ࡟᫂░࡞౵㣗ᓴᆅᙧࡀ㐃⥆ࡋ࡚ᙧᡂࡉࢀࡿ࡜ࡶ࡟ࠊ౵㣗ࡉࢀࡓ῱ὶෆ࡟ࡣᩘ⟠ᡤࡢ‪Ỉࡀ☜ㄆࡉࢀࡿࠋ෗┿ 㻝䠊౵㣗ᓴ≧ἣ㻌㸱㸬Ἑ㐨㛢ሰ㒊ࡢᏳᐃᛶ᳨ウ䠄䠍䠅᳨ウᴫせ㻌ᙜヱᆅ࡛ࡣ⌧ᅾࡶ኱つᶍ࡞Ἑ㐨㛢ሰ㒊ࡢ኱㒊ศ࡜ୖὶഃࡢࡓࡵụࡀṧᏑࡋ࡚࠾ࡾࠊ௒ᚋࡢ㇦㞵➼࡟ࡼࡿἙ㐨㛢ሰ㒊ࡢ୙Ᏻᐃ໬࡜ࡑࢀ࡟క࠺ᅵ▼ὶ➼ࡢ෌Ⓨࡀᠱᛕࡉࢀࡿࠋ⣖ఀ༙ᓥ኱Ỉᐖ᫬ࡢ⅏ᐖⓎ⏕せᅉ࡜ࡋ࡚ࡣࠊ⿕⅏᫬ࡢụỈ఩ୖ᪼ࡢ⑞㊧➼࠿ࡽἙ㐨㛢ሰ㒊ࡢኳ➃ࢆὶୗࡋࡓᆅ⾲Ỉ࡟㉺ὶ౵㣗࡟ࡼࡿྍ⬟ᛶࡀ㧗࠸࡜⪃࠼ࡽࢀ࡚࠸ࡿ
ࡀࠊࡑࢀ௨እࡢせᅉ࡜ࡋ࡚ࠊἙ㐨㛢ሰ㒊ࡢᾐ㏱◚ቯཬࡧࡍ࡭ࡾᔂቯࡶྰᐃ࡛ࡁ࡞࠸ࠋࡑࡇ࡛ྛ✀ᆅ㉁ㄪᰝ⤖ᯝࢆᇶ࡟ࠕ⌧ἣࠖࠕ⿕⅏๓ࠖࡢ  ࢣ࣮ࢫࢆᑐ㇟࡟ᾐ㏱◚ቯ࡜ࡍ࡭ࡾᔂቯࡢྍ⬟ᛶ࡟ࡘ࠸᳨࡚ウࢆ⾜ࡗࡓࠋ᳨ウࡢὶࢀࢆᅗ  ࡟♧ࡍࠋ䛆ᾐ㏱◚ቯ䛇㻌䛆䛩䜉䜚ᔂቯ䛇㻌᳨ウ᪉㔪䞉㻌䝰䝕䝹タᐃ㻌᳨ウ᪉㔪䞉㻌䝰䝕䝹タᐃ㻌
ㄪᰝ䝪䞊䝸䞁䜾
⌧ሙ㏱Ỉヨ㦂㻌
ᐊෆᅵ㉁ヨ㦂㻌

㪄㩷㪙㪄㪉㪐㪇㩷㪄≀ᛶ್タᐃ㻌
㏱Ỉಀᩘ➼㻌
ᾐ㏱ὶゎᯒ㻌䝰䝕䝹䞉≀ᛶ್෌⌧᳨ウ㻌≀ᛶ್タᐃ㻌
ᆅ┙ᐃᩘ➼㻌Ỉ఩タᐃ㻌Ᏻᐃゎᯒ㻌

ᾐ㏱◚ቯホ౯㻌䛩䜉䜚ᔂቯホ౯㻌ᅗ 㻞䠊Ἑ㐨㛢ሰ㒊Ᏻᐃᛶ᳨ウ䛾ὶ䜜㻌䠄䠎䠅᳨ウ⤖ᯝ㻌㻔㼍㻕ᾐ㏱◚ቯ㻌
ᾐ㏱◚ቯࡢ᳨ウࡣࠊᾐ㏱ὶゎᯒ࡟࡚ᚓࡽࢀࡓỈᖹཬࡧ㖄┤᪉ྥࡢືỈ໙㓄࡜ࠊᐊෆᅵ㉁ヨ㦂➼࠿ࡽ᥎ᐃࡋࡓᙜヱᆅࡢ㝈⏺ືỈ໙㓄ࢆẚ㍑࡟ࡼࡾホ౯ࡋࡓࠋᅗ 
ࡣᾐ㏱ὶゎᯒࡢ⤖ᯝࢆ♧ࡋࡓࡶࡢ࡛࠶ࡿࠋ㝈⏺ືỈ໙㓄 LF㸻 ࡟ᑐࡋࠊࠕ⌧ἣ࡛ࠖࡣỈᖹ᪉ྥ㸸⣙ ࠊ㖄┤᪉ྥ㸸⣙  ࡜኱ࡁࡃୗᅇࡗ࡚࠸ࡿࠋࡇࡢࡇ࡜࠿
ࡽࠊᙜヱᆅࡢ௒ᚋࡢᾐ㏱◚ቯࡢྍ⬟ᛶࡣᴟࡵ࡚ᑠࡉ࠸࡜࠸࠼ࡿࠋ୍᪉ࠊࠕ⿕⅏๓࡛ࠖࡣἲᑼ௜㏆࡟࡚ືỈ໙㓄ࡀ኱ࡁࡃ࡞ࡾࠊỈᖹ᪉ྥ㸸⣙ ࠊ㖄┤᪉ྥ㸸⣙ ࡜㝈⏺ືỈ໙㓄 LF ௨ୗ࡜࡞ࡿࡶࡢࡢࠊࠕ⌧ἣࠖ࡟ẚ࡭ࡿ࡜ᒁᡤⓗ࡞㛫㝽Ỉᅽࡀ⏕ࡌࡸࡍ࠸⤖ᯝ࡜࡞ࡗࡓࠋࡑࡋ࡚ࠕ⿕⅏๓ࠖࡢỈᖹ᪉ྥືỈ໙㓄ࡣἙᕝሐ㜵ᾐ㏱ὶ
᳨ウ୍࡛⯡ⓗ࡟⏝࠸ࡽࢀࡿࣃ࢖ࣆࣥࢢࡢチᐜ್㸦L㸻㸧࡟㏆࠸್ࢆ♧ࡋ࡚࠸ࡿࡇ࡜࠿ࡽࠊ⣖ఀ༙ᓥ኱Ỉᐖ᫬ࡢ୙Ᏻᐃ໬࡟ᾐ㏱◚ቯࡀ㛵୚ࡋ࡚࠸ࡓྍ⬟ᛶࡣṧࡿࠋ㻔㼎㻕䛩䜉䜚ᔂቯ㻌ࡍ࡭ࡾᔂቯ࡟㛵ࡋ࡚ࡣࠊᾐ㏱ὶゎᯒࡼࡾᚓࡽࢀࡓἙ㐨㛢ሰ㒊ࡢỈ఩ศᕸ࡜ᅵ㉁ᛶ≧࠿ࡽ᥎ᐃࡋࡓᆅ┙ᐃᩘࢆᇶ࡟Ᏻᐃゎᯒ㸦ಟṇࣇ࢙ࣞࢽ࢘ࢫ㸧ࢆ⾜ࡗࡓࠋゎᯒࡢ⤖ᯝࠊࠕ⌧ἣࠖࡣࠕ⿕⅏๓ࠖ࡜ẚ㍑ࡋ࡚Ἑ㐨㛢ሰ㒊ࡢᩳ㠃໙㓄ࡀ㠀ᖖ࡟⦆ࡃ࡞ࡗ࡚࠾ࡾᏳᐃഃ࡟స⏝ࡋࠊᏳ඲⋡ )V  ࡜࡞ࡿࠋ୍᪉ࠊࠕ⿕⅏๓ࠖࡣἙ㐨㛢ሰ㒊ࡢ໙㓄ࡀ᭱ࡶᛴ࡜࡞ࡿ㒊ศ࠿ࡘୖグᾐ㏱ὶゎᯒ࡟࠾ࡅࡿືỈ໙㓄ࡀ᭱ࡶ኱ࡁࡃ࡞ࡿ⟠ᡤ࡛᭱ࡶᏳ඲⋡ࡀపࡃ㸦)V 㸧ࠊ࡯ࡰ )V㸻 ࡟㏆࠸⤖ᯝ࡜࡞ࡗࡓࠋ௨ୖ࠿ࡽࠊᾐ㏱◚ቯ࡜ྠᵝ࡟ࡍ࡭ࡾᔂቯ࡟ࡘ࠸࡚
ࡶࠕ⌧ἣࠖࡣࠕ⿕⅏๓ࠖ࡟ẚ࡭Ᏻᐃᗘࡣ኱ࡁࡃྥୖࡋ࡚࠸ࡿࠋࡋ࠿ࡋࠊࠕ⿕⅏๓ࠖࡣ௒ᅇࡢ୍⯡್࡟ࡼࡿᏳᐃゎᯒࡢ⤖ᯝ࠿ࡽࡣ )VҸ ࡜࡞ࡗ࡚࠸ࡿࡇ࡜ࠊࡉࡽ࡟ᙅ⥺ࡀᾐ㏱ὶゎᯒ࡟࠾ࡅࡿືỈ໙㓄ࡀ᭱ࡶ኱ࡁࡃ࡞ࡿ⟠ᡤ࡜㔜」ࡋ࡚࠸ࡿࡇ࡜࠿ࡽࠊࡍ࡭ࡾᔂቯࡢᙳ㡪ࡶྰᐃ࡛ࡁ࡞࠸⤖ᯝ࡜࡞ࡗࡓࠋ㸲㸬ࡲ࡜ࡵཬࡧ௒ᚋࡢㄢ㢟
ձᾐ㏱ὶゎᯒࠊᏳᐃゎᯒࡢ⤖ᯝ࠿ࡽࠊࠕ⌧ἣࠖࡢᆅᙧ᮲௳࡛ࡣࠕ⿕⅏๓ࠖ࡟ẚ࡭ᾐ㏱◚ቯࠊࡍ࡭ࡾᔂቯ࡜ࡶᏳᐃᛶࡀ኱ࡁࡃྥୖࡋࠊᾐ㏱ࡸࡍ࡭ࡾ࡟ࡼࡿ
୙Ᏻᐃ໬ࡢྍ⬟ᛶࡣప࠸࡜࠸࠼ࡿࠋղ୍᪉ࠕ⿕⅏๓ࠖࡢ᮲௳࡛ࡣࠊἙ㐨㛢ሰ㒊ࡢ୙Ᏻᐃ໬
࡟ᾐ㏱◚ቯࡸࡍ࡭ࡾᔂቯࡀ㛵୚ࡋ࡚࠸ࡿྍ⬟ᛶࢆྰᐃ࡛ࡁ࡞࠸⤖ᯝ࡜࡞ࡗࡓࠋճᙜヱᆅ࡛ࡣ⌧ᅾ࣮࣎ࣜࣥࢢㄪᰝࡸỈ㉁ศᯒࠊ
ᙎᛶἼ᥈ᰝࠊ㟁Ẽ᥈ᰝ➼ࢆᐇ᪋୰࡛࠶ࡿࠋ௒ᚋࡣࠊྠㄪᰝ࣭᥈ᰝ⤖ᯝ࡜᩿ᒙࡸᆅ㉁ᵓ㐀ࢆຍ࿡ࡋࡓᆅ㉁࣭
Ỉ⌮ᵓ㐀ࡢ⢭ᰝࠊ኱⏿™ࡢヲ⣽࡞⅏ᐖ࣓࢝ࢽࢬ࣒㸦᫂἞༑ὠᕝ኱Ỉᐖࠊ⣖ఀ༙ᓥ኱Ỉᐖ㸧ࡢ᳨ウࢆ⾜࠺࡜࡜ࡶ࡟ࠊࡇࢀࡽࡢ⤖ᯝࢆ୰ྂ⏕ᒙศᕸᆅ࡟࠾ࡅࡿ῝ᒙᔂቯ࣭Ἑ㐨㛢ሰ༴㝤⟠ᡤᢳฟ࣭ホ౯ࡢ㔜せ࡞ᇶ♏ࢹ࣮ࢱྲྀᚓ࡟ࡘ࡞ࡆ࡚ࡺࡁࡓ࠸ࠋືỈ໙㓄䝧䜽䝖䝹㻝㻚㻜㼙㻛㼟㼑㼏ືỈ໙㓄㻔Ỉᖹ㻕䠖᭱኱⣙ 㻜㻚㻞䠘䠘㝈⏺ືỈ໙㓄 㼕㼏䠄㻝㻚㻜㻞䠅㻌ືỈ໙㓄䝧䜽䝖䝹㻝㻚㻜㼙㻛㼟㼑㼏ືỈ໙㓄㻔Ỉᖹ㻕䠖᭱኱⣙ 㻜㻚㻡䠘㝈⏺ືỈ໙㓄 㼕㼏䠄㻝㻚㻜㻞䠅㻌ᅗ 㻟䠊ᾐ㏱ὶゎᯒ䝧䜽䝖䝹ᅗ䠄ୖᅗ䠖䡞⌧ἣ䡟䠈ୗᅗ䠖䡞⿕⅏๓䡟䠅㻌ᆅ┙ᐃᩘ㻌䠘Ἑ㐨㛢ሰ㒊䠚㻌䞉䃒㻩㻝㻥㻚㻡㻔㼗㻺㻛㼙㻟㻕㻌䞉㻯㻩㻟㻜䠄㼗㻺㻛㼙㻞䠅㻌䞉䃥㻩㻟㻡䠄㼻䠅㻌䠘ᇶ┙㒊䠚㻌䞉䃒㻩㻞㻠㻚㻜㻔㼗㻺㻛㼙㻟㻕㻌䞉㻯㻩㻝㻜㻜䠄㼗㻺㻛㼙㻞䠅㻌䞉䃥㻩㻟㻤䠄㼻䠅㻌䛂⌧ἣ䛃㻌Ᏻ඲⋡ 㻲㼟㻩㻝㻚㻥㻠㻜㻌䛂⿕⅏๓䛃㻌Ᏻ඲⋡ 㻲㼟㻩㻝㻚㻜㻡㻤㻌ᅗ 㻠䠊Ᏻᐃゎᯒ⤖ᯝᅗ䠄ୖᅗ䠖䡞⌧ἣ䡟䠈ୗᅗ䠖䡞⿕⅏๓䡟䠅㻌౵㣗ᓴ䛾୧ᓊ䛿ᖖ᫬ᑠᔂቯ䚸ⴠ▼䜢⧞䜚㏉䛧䛶䛔䜛䚹㻌䛭䛾⤖ᯝ䚸ᓴ〈㒊䛻䛿ᓴ㗹≧䛾ᅵ◁䛜ከᩘศᕸ䛩䜛㺬㺼㺎㺶㺻㺖㺼⟠ᡤ‪ỈᆅⅬ ᥇Ỉ⟠ᡤ

1R

㻰㻌ࡓࡵụ㻰䇻㻌

1R
‪Ỉ

1R

1R
‪Ỉ

1R

1R

ࡓࡵụ

1R

1R

ᇶ┙䛾ᆅ㉁ᵓ㐀䛿㻌㉮ྥ䠖໭ᮾ㻙༡す᪉ྥ䠈㻌ഴᩳ䠖໭す㻌䋻ὶ䜜┙㻌᩿ᒙ䛻䜘䜛㐽Ỉ㻌䋻ᆅୗỈ఩䛾ୖ᪼㻌ᙎᛶἼ᥈ᰝ䛷䜒ప㏿ᗘᖏ䜢☜ㄆ㻌⋢ᇉෆ᩿ᒙ㻌㻭㻌ᅗ 㻡䠊኱⏿™㻌 ᆅᙧ䞉ᆅ㉁᳨ウᅗ㻌ཧ⪃ᩥ⊩ ⊂ ⏘ᴗᢏ⾡⥲ྜ◊✲ᡤᆅ㉁ㄪᰝ⥲ྜࢭࣥࢱ࣮ ୓ศࡢ  ᆅ㉁ᅗᖜࠕ㱟⚄ࠖཬࡧㄝ᫂᭩ ᆅᇦᆅ㉁◊✲ሗ࿌  㪄㩷㪙㪄㪉㪐㪈㩷㪄ࡓࡵụ ᥇Ỉ⟠ᡤቃ⏺䛿᫂░㻌㻭䇻㻌