❳ᕳࢆక࠺ᅇ㌿✚஘㞼㸦ࢫ࣮ࣃ࣮ࢭࣝ㸧ࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࢆㄪ࡭ࡿ⌮᝿໬ᩘ್ᐇ㦂ᮎ ᮌ ೺ ኴᮾி኱Ꮫ኱Ꮫ㝔⌮Ꮫ⣔◊✲⛉㸦⌧ᡤᒓ㸸⌮໬Ꮫ◊✲ᡤィ⟬⛉Ꮫ◊✲ᶵᵓ㸧㸯㸬ࡣࡌࡵ࡟ ❳ᕳࡣ㸪୍ᗘⓎ⏕ࡍࡿ࡜⏒኱࡞⿕ᐖࢆࡶࡓࡽࡍ኱Ẽ୰ࡢ⃭ࡋ࠸ ࡛࠶ࡿࡀ㸪✵㛫ࢫࢣ࣮ࣝࡢᑠࡉࡉ࡜ᑑ࿨ࡢ▷ࡉࡢࡓࡵ㸪ᩘ್ࣔࢹࣝ࡟ࡼࡿண ࡸ┤᥋ほ ࡣ౫↛ᅔ㞴࡛࠶ࡿ㸬୍᪉㸪㐣ཤ࡟Ⓨ⏕ࡋࡓ❳ᕳࢹ࣮ࢱࡢ⵳✚ࡸ㸪⢭ᗘࡢⰋ࠸኱Ẽࡢ෌ゎᯒࢹ࣮ࢱࡢⓏሙ࡟ࡼࡾ㸪❳ᕳࡢⓎ⏕⎔ቃሙࡢ⤫ィⓗ࡞◊✲ࡀྍ⬟࡜࡞ࡗ࡚ࡁࡓ㸬❳ᕳࡑࡢࡶࡢࡢຊᏛࢆ⌮ゎࡍࡿ࡜ྠ᫬࡟㸪❳ᕳࡢ㉳ࡇࡾࡸࡍ࠸⎔ቃሙࢆ᫂ࡽ࠿࡟ࡋ࡚࠸ࡃࡇ࡜ࡀ㸪❳ᕳ࡟ࡼࡿேⓗ⿕ᐖࢆ㍍ῶࡍࡿࡓࡵ࡟ᚲせ࡛࠶ࡿ㸬 ᙉ࠸❳ᕳࡢከࡃࡣ㸪㖄┤㍈ᅇࡾࡢᅇ㌿㸦࣓ࢯࢧ࢖ࢡࣟࣥ㸧ࢆෆ㒊࡟᭷ࡍࡿ≉Ṧ࡞✚஘㞼ࢫ࣮ࣃ࣮ࢭࣝ࡟కࡗ࡚⏕ࡌࡿ㸬࣓ࢯࢧ࢖ࢡࣟࣥࡣ㸪⎔ቃ㢼ࡢ㖄┤ࢩ࢔࡟క࠺Ỉᖹ ᗘࡀ㸪ୖ᪼ὶ࡟ࡼࡗ
࡚㖄┤᪉ྥ࡟❧ࡕୖࡆࡽࢀࡿࡇ࡜࡟ࡼࡗ࡚⏕ࡌࡿ㸬࣓ࢯࢧ࢖ࢡࣟࣥࡢ㉳※࡜࡞ࡿỈᖹ ᗘࡢ⥲㔞ࡣࠕࢫࢺ࣮࣒࡟┦ᑐⓗ࡞⎔ቃሙࡢ࣊ࣜࢩࢸ࢕㸦6WRUP5HODWLYH(QYLURQPHQWDO+HOLFLW\㸸65(+㸧ࠖ࡜࿧ࡤࢀࡿࣃ࣓࣮ࣛࢱ࡟ࡼࡗ࡚ぢ✚ࡶࡽࢀ㸪࣓ࢯࢧ࢖ࢡࣟࣥࡢᅇ㌿ࡢᙉࡉࡢᣦᶆ࡜࡞ࡿ㸬୍᪉㸪✚஘㞼ࡢୖ᪼ὶࡢᙉࡉࡣࠕᑐὶ᭷ຠ఩⨨࢚ࢿࣝࢠ࣮㸦&RQYHFWLYH$YDLODEOH3RWHQWLDO(QHUJ\㸸&$3(㸧ࠖ࡜࿧ࡤࢀࡿ኱Ẽᡂᒙࡢࣃ࣓࣮ࣛࢱ࡟ࡼࡗ࡚ぢ✚ࡶࡽࢀࡿ㸬୍⯡ⓗ࡟ࡣ㸪65(+ ࡸ &$3( ࡀ኱ࡁ࠸⎔ቃሙ࡯࡝ࢫ࣮ࣃ࣮ࢭࣝࡀ⏕ࡌࡸࡍࡃ㸪❳ᕳࡢⓎ⏕ࣜࢫࢡࡶ㧗࠸࡜⪃࠼ࡽࢀࡿ㸬᪥ᮏࡢ❳ᕳࡢ⣙ ࡣྎ㢼࡟కࡗ࡚Ⓨ⏕ࡍࡿ>@㸬ྎ㢼ࡣ㸪❳ᕳࡢ୺せ࡞Ⓨ⏕⎔ቃࡢ  ࡘ࡜࠸࠼ࡿࡀ㸪❳ᕳࢆከᩘⓎ⏕ࡉࡏࡿྎ㢼࡜㸪❳ᕳࢆ඲ࡃకࢃ࡞࠸ྎ㢼ࡀ࠶ࡾ㸪ࡑࡢ㐪࠸ࡀ⏕ࡌࡿせᅉࡣ༑ศ࡟ࡣ⌮ゎࡉࢀ࡚࠸࡞࠿ࡗࡓ㸬ᡃࠎࡢඛ⾜◊✲>@࡛ࡣ㸪᪥ᮏ࡛❳ᕳࢆⓎ⏕ࡉࡏࡓྎ㢼
㸦7RUQDGLF7\SKRRQ㸸77㸧࡜ࡑ࠺࡛࡞࠸ྎ㢼㸦1RQWRUQDGLF7\SKRRQ㸸17㸧ࡢ 65(+ ࡸ &$3( ࢆẚ㍑ࡋ㸪❳ᕳࡢⓎ⏕ࡀ㞟୰ࡍࡿྎ㢼໭ᮾ㇟㝈࡟࠾࠸࡚㸪77 ࡢ 65(+ ࡀ 17 ࡼࡾࡶ᭷ព࡟኱ࡁ࠸ࡇ࡜ࢆ♧ࡋࡓ㸦➨  ᅗ D㸧㸬୍᪉㸪㏻ᖖࡢィ⟬᪉ἲ࡟ࡼࡾ⟬ฟࡋࡓ &$3( ࡣ㸪❳ᕳࡢⓎ⏕ࡀẚ㍑ⓗᑡ࡞࠸ྎ㢼ࡢ༡ᮾഃ࡛኱ࡁࡃ㸪77 ࡢ್ࡀ 17 ࡟ẚ࡭኱ࡁ࠸ഴྥࡶぢࡽࢀ࡞࠿ࡗࡓࡀ㸦➨  ᅗ E㸧
㸪&$3(ࡢィ⟬࡟㸪✚஘㞼ࡢୖ᪼ὶࡀ࿘ᅖࡢ✵Ẽࢆྲྀࡾ㎸ࡴຠᯝ㸦࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ㸸(QWUDLQPHQW㸧ࢆຍ࿡ࡋࡓ (QWUDLQLQJ&$3(㸦(&$3(㸧ࢆㄪ࡭ࡓ࡜ࡇࢁ㸪(&$3( ࡣྎ㢼ࡢ໭ᮾ㇟㝈࡛኱ࡁࡃ㸪77
ࡢ᪉ࡀ 17 ࡼࡾࡶ᭷ព࡟኱ࡁࡃ࡞ࡗ࡚࠸ࡓ㸦➨  ᅗ F㸧
㸬&$3( ࡢィ⟬࡟࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࢆ⪃៖ࡍࡿࡇ࡜ࡀ㸪ྎ㢼࡟క࠺❳ᕳࡢⓎ⏕ࣜࢫࢡࢆホ౯ࡍࡿୖ࡛㔜せ࡛࠶ࡿࡇ࡜ࡀ㸪ึࡵ࡚♧၀ࡉࢀࡓ㸬 ゎᯒ࡛ࡣ㸪(&$3( ࡢィ⟬࡟⏝࠸ࡿ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆ  NPѸ ࡜ࡋࡓ㸬ࡋ࠿ࡋ࡞ࡀࡽࡇࡢ್ࡣ㸪(&$3( ࡢ✵㛫ศᕸ࡜❳ᕳࡢⓎ⏕఩⨨ศᕸ࡜ࡢᩚྜᛶࡢほⅬ࠿ࡽᑟධࡋࡓ್࡛࠶ࡾ㸪ᐇ㝿ࡢࢫ࣮ࣃ࣮ࢭࣝࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡࡟ᇶ࡙ࡃࡶࡢ࡛ࡣ࡞࠿ࡗࡓ㸬࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࡣ㸪✚஘㞼ഃ㠃࡛⏕ࡌࡿ஘ὶΰྜ࡜㸪ࢫ࣮ࣃ࣮ࢭࣝࡢ⛣ື࡟┦ᑐⓗ࡞⎔ቃ㢼ࡢ㞼ෆ㒊࡬ࡢ྿㎸ࡳ࡟ࡼࡗ࡚⏕ࡎࡿ࡜⪃࠼ࡽࢀࡿࡀ㸪ࡑࡢ㔞ࢆほ ࡟ࡼࡾぢ✚ࡶࡿࡇ࡜ࡣᅔ㞴࡛࠶ࡾ㸪ᩘ್ࣔࢹࣝࢆ⏝࠸ࡓࢩ࣑࣮ࣗࣞࢩࣙࣥࢆ⾜࠺ᚲせࡀ࠶ࡿ㸬ィ⟬࡟ࡣ㸪ࢫ࣮ࣃ࣮ࢭࣝ࡜ࡑࡢ⎔ቃሙࢆ⾲⌧ࡍࡿ NPᅄ᪉⛬ᗘࡢィ⟬㡿ᇦ࡜㸪஘ὶΰྜ࡟ࡼࡿ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࢆ㝧࡟⾲⌧ࡍࡿ P ⛬ᗘࡢ✵㛫ゎ

スーパーコンピューティングニュース- 38 -Vol.19,No.52017➨  ᅗ㸸❳ᕳࢆక࠺ྎ㢼㸦77㸧࡜ࡑ࠺࡛࡞࠸ྎ㢼㸦17㸧ࡢࣃ࣓࣮ࣛࢱࡢᖹᆒ✵㛫ศᕸࡢẚ㍑
D 㸸ྎ㢼࿘㎶ࡢ 65(+ ࡢศᕸ㸬ᕥࡣ 77㸪ྑࡣ 17 ࡟ࡘ࠸࡚㸬77 ࡢᅗ୰ࡢⓑ୸ࡣ㸪ྎ㢼୰ᚰ࡟┦ᑐⓗ࡞❳ᕳࡢⓎ⏕఩⨨ࢆ♧ࡋ㸪㯮ᐇ⥺ࡢࢥࣥࢱ࣮ࡣ㸪77 ࡢ 65(+ ࡀ 17 ࡟ẚ࡭㸪Ỉ‽࡛᭷ព࡟኱ࡁ࠸㡿ᇦࢆ⾲ࡍ㸬 E 㸸 D ࡜ྠࡌ㸬ࡓࡔࡋ㏻ᖖࡢ &$3( ࡟ࡘ࠸࡚㸬77 ࡢᅗ୰ࡢ㯮◚⥺ࡢࢥࣥࢱ࣮ࡣ㸪77 ࡢ &$3( ࡀ 17 ࡟ẚ࡭㸪Ỉ‽࡛᭷ព࡟ᑠࡉ࠸㡿ᇦࢆ⾲ࡍ㸬 F 㸸 D ࣭ E ࡜ྠࡌ㸬ࡓࡔࡋ㸪࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࢆ⪃៖ࡋࡓ &$3(㸦(&$3(㸧࡟ࡘ࠸࡚㸬ീᗘࡀᚲせ࡛࠶ࡾ㸪ࢫ࣮ࣃ࣮ࢥࣥࣆ࣮ࣗࢱ࣮ࡢ฼⏝ࡀ୙ྍḞࡔ㸬ᮏ◊✲ࡢ┠ⓗࡣ㸪㧗ゎീᗘࡢ⌮᝿໬ᩘ್ᐇ㦂࡟ࡼࡾࢫ࣮ࣃ࣮ࢭࣝࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆ᫂ࡽ࠿࡟ࡋ㸪(&$3( ࡢィ⟬࡛⏝࠸ࡓ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࡢ≀⌮ⓗ࡞⿬௜ࡅࢆᚓࡿࡇ࡜࡛࠶ࡿ㸬

スーパーコンピューティングニュース- 39 -

Vol.19,No.5

2017ᐇ㦂タᐃ ᮏ◊✲࡛ࡣ㸪㠀㟼ຊᏛẼ㇟ࣔࢹࣝ &0 YHUࢆ౑⏝ࡋࡓ㸬✚஘㞼ഃ㠃࡛⏕ࡎࡿ஘ὶΰྜࢆ㝧࡟⾲⌧ࡍࡿࡓࡵ㸪Ỉᖹ࣭㖄┤᱁Ꮚ㛫㝸ࢆ P㸪✚ศࡢ᫬㛫ࢫࢸࢵࣉࢆ V㸦㡢Ἴࡣ V㸧࡜ࡋࡓ㸬ィ⟬㡿ᇦ࡜ࡋ࡚Ỉᖹ NP ᅄ᪉㸪㖄┤ NP㸦ࡓࡔࡋ㧗ᗘ NP ࡼࡾୖࡣ㸪㢼㏿࣭ ఩ࢆᇶᮏሙࡢ್࡟ᙉไࡍࡿ 5D\OHLJK GDPSLQJ ᒙ㸧ࢆ☜ಖࡋ㸪ഃ㠃ቃ⏺ࡣゎᨺቃ⏺㸪ୗ㒊࣭ୖ㒊ቃ⏺ࡣ⮬⏤⁥ࡾ࡜ࡋࡓ㸬ࢧࣈࢢࣜࢵࢻࡢ஘ὶ㐠ື࢚ࢿࣝࢠ࣮ࡣ 'HDUGRUII ࡢࢫ࣮࣒࢟>@࡟ࡼࡾணሗࡍࡿ㸬㞼ᚤ≀⌮㐣⛬ࡢ⾲⌧࡟ࡣ㸪㞼Ỉ࣭㞵࣭㞼ị࣭㞷࣭㞿ࢆணሗࡍࡿ 0RUULVRQ ࡢࢲࣈ࣮࣓ࣝࣔࣥࢺࣂࣝࢡࢫ࣮࣒࢟>@>@ࢆ⏝࠸ࡓ㸬 ᐇ㦂࡛ࡣ㸪ࢫ࣮ࣃ࣮ࢭࣝࡢⓎ⏕࡟㐺ࡋࡓ኱Ẽࣉࣟࣇ࢓࢖ࣝࢆỈᖹ୍ᵝ࡟୚࠼㸪ᅇ㌿ᴃ෇యᆺࡢ఩ᨐ஘㸦୰ᚰ࡛.㸧࡟ࡼࡗ࡚ᑐὶࢆບ㉳ࡋ㸪ࢫ࣮ࣃ࣮ࢭࣝࢆⓎ⏕ࡉࡏࡓ㸬኱Ẽࣉࣟࣇ࢓࢖ࣝ࡟ࡣ㸪 ᖺ  ᭶  ᪥࡟ྎ㢼  ྕ࡟కࡗ࡚」ᩘࡢࢫ࣮ࣃ࣮ࢭ࣭ࣝ❳ᕳࡀ㛵ᮾᆅ᪉࡛Ⓨ⏕ࡋࡓ⎔ቃሙࢆ௦⾲ࡍࡿ㧗ᒙほࢹ࣮ࢱ㸦 -67㸪㤋㔝㸧ࢆᖹ⁥໬ࡋࡓࣉࣟࣇ࢓࢖ࣝࢆ⏝࠸ࡓ㸬ࡓࡔࡋ㸪ࢫ࣮ࣃ࣮ࢭࣝࡀィ⟬㡿ᇦእ࡟ฟ࡚࠸ࡃࡇ࡜ࢆ㜵ࡄࡓࡵ㸪Ỉᖹ㢼㏿࡟ࡣ㸪ࢫ࣮ࣃ࣮ࢭࣝࡢ⛣ື㏿ᗘࢆ㖄┤୍ᵝ࡟ᕪࡋᘬ࠸ࡓ್ࢆ⏝࠸ࡓ㸬ィ⟬⤖ᯝࡢᴫせ ➨  ᅗࡣ㸪✚ศ㛤ጞ  ศᚋ࡟࠾ࡅࡿ㖄┤✚⟬จ⤖≀㔞㸦ࢩ࢙࣮ࢻ㸪NJPѸ㸧㸪ࣔࢹࣝ᭱ୗᒙࡢ఩ᨐ஘ࡀѸ. ࡢࢥࣥࢱ࣮㸦ᐇ⥺㸧ࢆ⾲ࡋ࡚࠾ࡾ㸪ࡑࢀࡒࢀ㞼㸪✚஘㞼ࡀసࡾฟࡍ෭ẼእฟὶࡢᵝᏊࢆ♧ࡋ࡚࠸ࡿ㸬୰ᚰ௜㏆ࡢ࡭ࡓሬࡾ㒊ศࡣ㸪㧗ᗘ⣙  NP ࡢจ⤖≀ΰྜẚࡀ Ѹ NJ
NJѸ ௨ୖࡢ㡿ᇦࢆ♧ࡋ࡚࠾ࡾ㸪Ẽ㇟࣮ࣞࢲ࣮࡛ᤊ࠼ࡽࢀࡿ㞵ỈࡢᵝᏊࢆᶍࡋ࡚࠸ࡿ㸬✚஘㞼ࡢ༡➃࡛ࡣ㞵Ỉศᕸࡀࣇࢵࢡ≧࡟‴᭤ࡋ࡚࠸ࡿࡀ㸪ࡇࢀࡣᅇ㌿ࡍࡿ㢼࡟㞵Ỉࡀὶࡉࢀࡿࡇ࡜࡛⏕ࡌࡓᙧ≧࡛࠶ࡾ㸪࣓ࢯࢧ࢖ࢡࣟࣥࢆ᭷ࡍࡿࢫ࣮ࣃ࣮ࢭࣝࡢ඾ᆺⓗ࡞≉ᚩࢆ♧ࡋ࡚࠸ࡿ㸬ࢫ࣮ࣃ࣮ࢭࣝ➨  ᅗ㸸෌⌧ࡉࢀࡓࢫ࣮ࣃ࣮ࢭࣝࡢᵝᏊ ✚ศ㛤ጞ  ศᚋ࡟࠾ࡅࡿ㖄┤✚⟬จ⤖≀㔞㸦ࢩ࢙࣮ࢻ㸪NJPѸ㸧࡜㸪ࣔࢹࣝ᭱ୗᒙࡢ ఩ᨐ஘ࡀѸ. ࡢࢥࣥࢱ࣮㸦ᐇ⥺㸧㸬୰ᚰ௜㏆ࡢ࡭ࡓሬࡾ㒊ศࡣ㸪㧗ᗘ⣙ NP ࡢจ⤖≀ΰྜẚࡀ ѸNJNJѸ ௨ୖࡢ㡿ᇦ㸬⡿ᅜ኱Ẽ◊✲ࢭࣥࢱ࣮㸦1DWLRQDO&HQWHUIRU$WPRVSKHULF5HVHDUFK㸸1&$5㸧ࡢ *HRUJH%U\DQẶࡀ㛤Ⓨ࣭⟶⌮ࡋ࡚࠸ࡿẼ㇟ࣔࢹࣝ㸬Ặࡢ࢙࢘ࣈ࣮࣌ࢪୖ࠿ࡽࢲ࣮࢘ࣥࣟࢻࡀྍ⬟࡛࠶ࡿ
㸦KWWSZZZPPPXFDUHGXSHRSOHEU\DQFP㸧㸬
スーパーコンピューティングニュース- 40 -

Vol.19,No.52017ෆ㒊࡟࠾ࡅࡿୖ᪼ὶࡢ᭱኱್ࡢ᫬㛫㧗ᗘ᩿㠃ࢆぢࡿ࡜㸦➨  ᅗ㸧㸪 ศ㡭࠿ࡽୖ᪼ὶࡀᙉ໬ࡉࢀ㸪ࡑࡢᚋࡣ᩿⥆ⓗ࡞ᙉ࠸ୖ᪼ὶࡀ⥔ᣢࡉࢀ࡚࠸ࡿ㸬ࡲࡓ㸪ࣔࢹࣝ᭱ୗᒙ࡟࠾ࡅࡿ㖄┤ ᗘࡢ᭱኱್ࡢ᫬⣔ิࢆぢࡿ࡜㸦➨  ᅗ㸧㸪 ศ࠿ࡽ  ศ࡟࠿ࡅ࡚ ᗘࡀᙉࡲࡿᵝᏊࡀぢࡽࢀࡿ㸬ࡇࡢ᫬㛫ᖏࡢὶࢀሙࢆヲ⣽࡟ㄪ࡭ࡓ࡜ࡇࢁ㸪ᆅ⾲㠃࠿ࡽ㞼ᗏ࡟ఙࡧࡿ❳ᕳ≧ࡢ ࡀ☜ㄆࡉࢀࡓ㸬ᮏィ⟬࡛ࡣ㸪⌮᝿ⓗ࡞⎔ቃሙࡢୗ㸪❳ᕳ≧ ࢆక࠺‽ᐃᖖⓗ࡞ࢫ࣮ࣃ࣮ࢭࣝࡢ෌⌧࡟ᡂຌࡋࡓ࡜࠸࠼ࡿ㸬➨  ᅗ㸸ࢫ࣮ࣃ࣮ࢭࣝෆ㒊࡟࠾ࡅࡿୖ᪼ὶࡢ᭱኱್ࡢ᫬㛫㧗ᗘ᩿㠃ᶓ㍈ࡣ᫬㛫㸦PLQ㸧㸪⦪㍈ࡣ㧗ᗘ㸦NP㸧
㸬ࢥࣥࢱ࣮ࡣ PVѸ ࡈ࡜㸬➨  ᅗ㸸ࣔࢹࣝ᭱ୗᒙ࡟࠾ࡅࡿ㖄┤ ᗘࡢ᭱኱್ࡢ᫬⣔ิᶓ㍈ࡣ᫬㛫㸦PLQ㸧㸪⦪㍈ࡣᗘ㸦VѸ㸧㸬࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࡢぢ✚ࡶࡾᮏ◊✲࡛ࡣ㸪㖄┤ὶ㏿ࡀ PVѸ ࢆ㉸࠼ࡿ㐃⥆ⓗ࡞ୖ᪼ὶᇦࢆࢫ࣮ࣃ࣮ࢭࣝࡢୖ᪼ὶࢥ࢔࡜ᐃ⩏ࡋ㸪ゎᯒᑐ㇟࡜ࡋࡓ㸬ୖ᪼ὶࢥ࢔ࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆぢ✚ࡶࡿࡓࡵ㸪⃰ᗘࡀ㧗ᗘ࡜ඹ࡟�⥺ᙧ࡟ῶᑡࡍࡿࡼ࠺࡞ࢺ࣮ࣞࢧ࣮�

� =1−�� for � � �� �   ࡜ࡋࡓ㸬୍᪉㸪ୖ᪼ὶࢥࢆึᮇ᫬้࡟୚࠼࡚࠸ࡿ㸬ࡓࡔࡋ㸪+ ࡣ NP ࡜ࡋ㸪]!+ ࡛ࡣ�� ࡜᭩ࡃ࡜㸪࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡Ȝ࡛⎔ቃሙࡢ✵Ẽࢆྲྀࡾ㎸ࡴሙ࢔ෆ㒊ࡢࢺ࣮ࣞࢧ࣮⃰ᗘࢆ�� ࡢ㧗ᗘኚ໬ࡣ㸪ᐃᖖ≧ែࢆ௬ᐃࡍࢀࡤྜࡢ�

スーパーコンピューティングニュース- 41 -

Vol.19,No.52017

�
�
=�



� −�
� �

 ࢆ‶ࡓࡍ㸬Ȝࡀᐃᩘ࡞ࡽࡤ㸪  ᘧࡢୗ㸪  ᘧࡢゎᯒゎ
� =1−
��
�

11−
� 

ࢆᚓࡿ㸬ࡓࡔࡋ㸪] ࡣୖ᪼ὶࢥ࢔ࡢ㉳Ⅼ㧗ᗘ࡛࠶ࡿ㸬ᵝࠎ࡞Ȝ࡟ᑐᛂࡍࡿ  ᘧࡢࣉࣟࣇ࢓࢖ࣝࢆ➨  ᅗ࡟♧ࡍ㸬➨  ᅗ㸸ୖ᪼ὶࢥ࢔ෆ࡟࠾ࡅࡿࢺ࣮ࣞࢧ࣮⃰ᗘࡢ㧗ᗘኚ໬ࡢゎᯒゎ ᘧࢆࣉࣟࢵࢺࡋࡓࡶࡢ㸬ྑ࠿ࡽ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡Ȝ 㸪㸪͐㸪NPѸ ࡢሙྜ㸬ࡓࡔࡋ㸪ୖ᪼ὶࢥ࢔ࡢ㉳Ⅼ㧗ᗘ ] ࡣ P ࡜ࡋࡓ㸬ྑୗࡢ➃࠿ࡽᕥୖࡢ➃࡬ᘏࡧࡿ┤⥺ࡣ㸪  ᘧࡢ⎔ቃሙࡢࣉࣟࣇ࢓࢖ࣝ㸬 ᮏ◊✲࡛ࡣ㸪‽ᐃᖖ≧ែࡀ⥔ᣢࡉࢀࡓ ̽ ศ࡟࠾ࡅࡿୖ᪼ὶࢥ࢔ෆࡢࢺ࣮ࣞࢧ࣮⃰ᗘศᕸ࠿ࡽ㸪࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆぢ✚ࡶࡗࡓ㸬➨  ᅗ࡟㸪̽ ศ࡟࠾ࡅࡿୖ᪼ὶࢥ࢔ෆࡢྛ㧗ᗘࡢࢺ࣮ࣞࢧ࣮⃰ᗘࡢ☜❧ᐦᗘศᕸࢆ♧ࡍ㸬ᐇ⥺ࡣୖ᪼ὶෆ㒊ࡢࢺ࣮ࣞࢧ࣮⃰ᗘࡢᖹᆒࣉࣟࣇ࢓� ࡟┦ᙜ㸧� 㸧࡛࠶ࡿ㸬㧗ᗘ⣙ NP ௜㏆ࢆ㉳Ⅼ࡟㸪⎔࢖ࣝ㸦�㸪Ⅼ⥺ࡣ⎔ቃሙࡢࣉࣟࣇ࢓࢖ࣝ㸦�ቃሙࡢ✵Ẽࢆྲྀࡾ㎸ࡳ࡞ࡀࡽ㸪ୖ᪼ὶෆ㒊ࡢࢺ࣮ࣞࢧ࣮⃰ᗘࡀ㧗ᗘ࡜ඹ࡟ῶᑡࡍࡿᵝᏊࡀぢࡽࢀࡿ㸬ࢩ࣑࣮ࣗࣞࢩ࡛ࣙࣥᚓࡽࢀࡓୖ᪼ὶࢥ࢔ෆࡢᖹᆒࣉࣟࣇ࢓࢖ࣝ࡜㸪ゎᯒゎ࡜ࢆẚ㍑ࡍࡿ࡜㸦➨ ᅗ㸧㸪㧗ᗘ NP ⛬ᗘࡲ࡛ࡣ࠾ࡼࡑ NPѸ ࡢ⥺࡟ἢ࠸㸪㧗ᗘ NP ⛬ᗘ࡛ࡣ NPѸ ࡛ୖ᪼ࡋࡓሙྜࡢ್࡜࡞ࡗ࡚࠸ࡿ㸬㧗ᗘ NP ࢆ㉸࠼ࡿ࡜㸪ࢹࢺࣞ࢖࣓ࣥࣥࢺ㸦'HWUDLQPHQW㸸㞼ෆ㒊࠿ࡽ⎔ቃሙ࡬ࡢ✵Ẽࡢὶฟ㸧ࡀᨭ㓄ⓗ࡟࡞ࡾ㸪  ᘧࡀᡂࡾ❧ࡓ࡞ࡃ࡞ࡿࡀ㸪ᑐὶᅪ୰ᒙࡲ࡛ࡢࢫ࣮ࣃ࣮ࢭࣝࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࡣ ̽NPѸ ࡛࠶ࡿ࡜ぢ✚ࡶࡽࢀ㸪ᡃࠎࡀ (&$3( ࡢィ⟬࡛⏝࠸ࡓ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡㸦NPѸ㸧ࡢጇᙜᛶࡀ☜࠿ࡵࡽࢀࡓ㸬ࡲ࡜ࡵ࡜௒ᚋࡢᒎᮃ ᮏ◊✲࡛ࡣ㸪✚஘㞼ࡢୖ᪼ὶᙉᗘࡢ࣏ࢸࣥࢩࣕࣝࢆ⾲ࡍࣃ࣓࣮ࣛࢱ &$3( ࡟࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺࡢຠᯝࢆຍ࿡ࡋࡓ (QWUDLQLQJ&$3(㸦(&$3(㸧ࡀ㸪ྎ㢼࡟క࠺❳ᕳࡢⓎ⏕ࣜࢫࢡࢆホ౯ࡍࡿⰋ࠸ᣦᶆ࡟࡞ࡿ࡜࠸࠺ᡃࠎࡢඛ⾜◊✲ࢆᛕ㢌࡟㸪(&$3( ࡢィ⟬࡟⏝࠸ࡓ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡㸦NPѸ㸧ࡢ≀⌮ⓗ࡞⿬௜ࡅࢆᚓࡿࡓࡵ㸪❳ᕳࢆ⏕ࡎࡿᅇ㌿✚஘㞼ࢫ࣮ࣃ࣮ࢭࣝࡢ㧗ゎീᗘ⌮᝿໬ᩘ

スーパーコンピューティングニュース- 42 -

Vol.19,No.52017➨  ᅗ㸸̽ ศ࡟࠾ࡅࡿୖ᪼ὶࢥ࢔ෆࡢྛ㧗ᗘࡢࢺ࣮ࣞࢧ࣮⃰ᗘࡢ☜❧ᐦᗘศᕸ�࡟ ࢩ࢙࣮ࢻࡣ᭱኱್࡛つ᱁໬ࡋࡓ☜❧ᐦᗘศᕸ㸬ᐇ⥺ࡣୖ᪼ὶෆ㒊ࡢࢺ࣮ࣞࢧ࣮⃰ᗘࡢᖹᆒࣉࣟࣇ࢓࢖ࣝ㸦�� 㸧࡛࠶ࡿ㸬ᶓ㍈ࡣࢺ࣮ࣞࢧ࣮⃰ᗘ㸪⦪㍈ࡣ㧗ᗘ㸦NP㸧┦ᙜ㸧㸪Ⅼ⥺ࡣ⎔ቃሙࡢࣉࣟࣇ࢓࢖ࣝ㸦�㸬➨  ᅗ㸸ࢩ࣑࣮ࣗࣞࢩ࡛ࣙࣥᚓࡽࢀࡓୖ᪼ὶࢥ࢔ෆࡢᖹᆒࣉࣟࣇ࢓࢖ࣝ࡜㸪ゎᯒゎ࡜ࡢẚ㍑
 㯮ᐇ⥺ࡣࢩ࣑࣮ࣗࣞࢩࣙࣥࡢ⤖ᯝ㸬⅊Ⰽࡢ⥺ࡣྑ࠿ࡽ㡰࡟Ȝ 㸪㸪͐㸪NPѸ ࡢሙྜࡢ  ᘧࡢゎᯒゎ㸬ྑୗࡢ➃࠿ࡽᘏࡧࡿ┤⥺ࡣ㸪  ᘧࡢ⎔ቃሙࡢࣉࣟࣇ࢓࢖ࣝ㸬್ᐇ㦂ࢆᐇ᪋ࡋ㸪ࡑࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆ᳨ドࡋࡓ㸬ᐇ㦂࡛ࡣ㸪 ᖺࡢྎ㢼  ྕ࡟క࠸㛵ᮾᆅ᪉࡛」ᩘࡢࢫ࣮ࣃ࣮ࢭ࣭ࣝ❳ᕳࡀⓎ⏕ࡋࡓ⎔ቃሙࡢୗ㸪❳ᕳ≧ ࢆక࠺‽ᐃᖖⓗ࡞ࢫ࣮ࣃ࣮ࢭࣝࢆⓎ⏕࣭⥔ᣢࡉࡏࡿࡇ࡜࡟ᡂຌࡋࡓ㸬ึᮇ᫬้࡟㧗ᗘ࡜ඹ࡟⃰ᗘࡀῶᑡࡍࡿࢺ࣮ࣞࢧ࣮ࢆ୚࠼㸪‽ᐃᖖ≧ែ࡟ⴠࡕ╔࠸ࡓࢫ࣮ࣃ࣮ࢭࣝࡢୖ᪼ὶෆ㒊࡟࠾ࡅࡿࢺ࣮ࣞࢧ࣮⃰ᗘࡢ㧗ᗘኚ໬࠿ࡽ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆぢ✚ࡶࡗࡓ࡜ࡇࢁ㸪ࢹࢺࣞ࢖࣓ࣥࣥࢺࡀᨭ㓄ⓗ࡜࡞ࡿᑐὶᅪ୰ᒙࡲ࡛࡛ ̽NPѸ ⛬ᗘ࡜࡞ࡾ㸪(&$3( ࡢィ⟬࡛⏝࠸ࡓ್ࢆᨭᣢࡍࡿ⤖ᯝࢆᚓࡓ㸬 ᮏ◊✲࡛ࡣ㸪᪥ᮏࡢྎ㢼࡟క࠺ࢫ࣮ࣃ࣮ࢭࣝ࡟ࡘ࠸࡚ゎᯒࢆ⾜ࡗࡓࡀ㸪⡿ᅜࡢࣁࣜࢣ࣮ࣥ࡟క࠺ࢫ࣮ࣃ࣮ࢭࣝࡸ㸪 ᖏపẼᅽ࡞࡝௚ࡢ⎔ቃሙ࡛Ⓨ⏕ࡍࡿࢫ࣮ࣃ࣮ࢭࣝ࡟ᑐࡋ࡚ࡶྠᵝࡢゎᯒࢆ

スーパーコンピューティングニュース- 43 -

Vol.19,No.52017⾜࠸㸪⎔ቃሙࡈ࡜ࡢ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࢆ᫂ࡽ࠿࡟ࡋ࡚࠸ࡃᚲせࡀ࠶ࡿ㸬ࡲࡓ㸪኱Ẽᡂᒙࡸ㢼ࡢ㖄┤ࢩ࢔ࡢ㐪࠸࡟ࡼࡿ࢚ࣥࢺࣞ࢖࣓ࣥࣥࢺ⋡ࡢ⎔ቃሙ౫Ꮡᛶࢆᐃ㔞໬ࡋ㸪(&$3( ࡢィ⟬࡟㐺ษ࡟ࣃ࣓ࣛࢱࣛ࢖ࢬࡍࡿࡇ࡜࡛㸪(&$3( ࡢ᭷ຠᛶࡀࡉࡽ࡟㧗ࡲࡾ㸪❳ᕳ࡞࡝ࡢࢩࣅ࢔⌧㇟ࡢணሗ⢭ᗘྥୖ࡬࡜ᐤ୚ࡍࡿࡇ࡜ࡀᮇᚅࡉࢀࡿ㸬ㅰ ㎡ᮏ◊✲ࡢᩘ್ィ⟬ࡣ㸪ᮾி኱Ꮫ᝟ሗᇶ┙ࢭࣥࢱ࣮ࡢ ); ୖ࡛ᐇ⾜ࡉࢀࡓ㸬ࡲࡓ㸪ᮏ◊✲ࡢ୍㒊ࡣ㸪ᮾி኱Ꮫ᝟ሗᇶ┙ࢭࣥࢱ࣮ᖹᡂ  ᖺᗘᚋᮇࠕࢫ࣮ࣃ࣮ࢥࣥࣆ࣮ࣗࢱ࣮ⱝᡭ࣭ዪᛶ฼⏝⪅᥎⸀ࠖㄢ㢟࡟ࡼࡗ࡚⾜ࢃࢀࡓࡶࡢ࡛࠶ࡿ㸬ᮏෆᐜࡣ㸪⚾ࡢ༤ኈㄢ⛬࡟࠾ࡅࡿ◊✲ࡢ୍㒊࡛࠶ࡾ㸪ᣦᑟᩍဨ࡛࠶ࡿ᪂㔝ᏹᩍᤵ㸦ᮾி኱Ꮫ኱Ẽᾏὒ◊✲ᡤ㸧࡟ࡣከࡃࡢࡈᣦᑟ࣭ࡈຓゝࢆ࠸ࡓࡔ࠸ࡓ㸬ཧ ⪃ ᩥ ⊩>@1LLQR+7)XMLWDQLDQG1:DWDQDEH$VWDWLVWLFDOVWXG\RIWRUQDGRHVDQGZDWHUVSRXWVLQ-DSDQIURPWR-&OLPDWH̽
>@6XHNL.DQG+1LLQR7RZDUGEHWWHUDVVHVVPHQWRIWRUQDGRSRWHQWLDOLQW\SKRRQV 6LJQLILFDQFH RI FRQVLGHULQJ HQWUDLQPHQW HIIHFWV IRU &$3( *HRSK\VLFDO

5HVHDUFK/HWWHUV̽
>@ 'HDUGRUII - :  6WUDWRFXPXOXVFDSSHG PL[HG OD\HU GHULYHG IURP D WKUHH
GLPHQVLRQDOPRGHO%RXQG/D\HU0HWHRU̽
>@ 0RUULVRQ + - $ &XUU\ DQG 9 , .KYRURVW\DQRY  $ QHZ GRXEOHPRPHQW
PLFURSK\VLFVSDUDPHWHUL]DWLRQIRUDSSOLFDWLRQLQFORXGDQGFOLPDWHPRGHOVSDUW,'HVFULSWLRQ-$WPRV6FL̽
>@0RUULVRQ+*7KRPSVRQDQG97DWDUVNLL,PSDFWRIFORXGPLFURSK\VLFVRQ
WKHGHYHORSPHQWRIWUDLOLQJVWUDWLIRUPSUHFLSLWDWLRQLQDVLPXODWHGVTXDOOOLQH
&RPSDULVRQRIRQHDQGWZRPRPHQWVFKHPHV0RQ:HD5HY̽

スーパーコンピューティングニュース- 44 -

Vol.19,No.52017