Reasons to believe that P is not equal to NP.

Question

There are lists of reasons to believe that P is not equal to NP. But they are somewhat "metaphysical". Are there more mathematically rigorous reasons?

Answer 1

Yes, here is one.
Let's assume that Subset sum problem allows some form of "divide and conquer" approach. Below is example of sequence of sorted sums and corresponding sequences:
$0 < a1 < a2 < a1 + a2 < a3 < a1 + a3 < a2 + a3 < a1 + a2 + a3$ # assume all sums are different
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
000, 100, 010, 110, 001, 101, 011, 111

Each sequence of numbers can be transformed in this way to sequence of bit strings. If we can get any bit of this sequence in polynomial time than Subset sum is solvable in polynomial time. Let's represent this problem in geometrical language. Each sorted sequence of sums correspond to chamber in hyperplane arrangement $HA3$, having all hyperplanes with normal vectors, consisting of -1, 0, and 1. We should somehow subdivide $HA3$ to obtain area of space with only those chambers and parts of chambers, which have the same value of desired bit. This problem is computationally demanding even for 6 numbers, so I considered other problem: How many cutting hyperplanes do we need to isolate every chamber in $HA2$ (having normal vectors, consisting of -1 and 1). More precisely in area of $HA2$ without symmetries, see get_base_simplex() function. Number that we interested in is minimum depth of all possible subdivision trees. For example if number of chambers is 14 than minimum depth cannot be less than 4, but it will be probably more, because hyperplanes are not orthogonal and chambers are arranged in intricate configuration. First I used only hyperplanes of $HA2$ to subdivide $HA2$, then hyperplanes of HA3, but resulting tree depths are the same. And, alas, they are exponential:
n = 3: 1; n = 4: 2; n = 5: 3, n = 6: 5, n = 7: 8.
It seems that this is sequence which have the same values eventually as sequence of facet counts of "most complex chamber" of $HA2$ (see get_mcc2_point()). These facet counts are:
n = 3: 4; n = 4: 4; n = 5: 5; n = 6: 6; n = 7: 8; n = 8: 13; n = 9: 23; n = 10: 40.
But because of computational difficulties I cannot state for sure that tree depth for $HA3$ is exponential. Below is Python code for computing tree depth for $HA2$.

EDIT Added divide_ha2_by_vectors_3_breadth_first() function
EDIT 2 Added separate_mcp2() which separates most complex region and searches only through part of tree.

from __future__ import division, print_function
from fractions import gcd
from itertools import product
from random import randint, random


enum = enumerate

def nums(list_):
    return range(len(list_))

def get_list_gcd(l):
    res = abs(reduce(gcd, l))
    return res

def get_sp(v0, v1):
    res = sum([v0[i] * v1[i] for i in nums(v0)])
    return res

def sum_lists(lists):
    res = type(lists[0])([sum([lists[y][x] for y in nums(lists)]) for x in nums(lists[0])])
    return res

def mul_list(l, koeff):
    res = [koeff * elt for elt in l]
    if type(l) == type(()):
        res = tuple(res)
    return res

def get_vectors_3(n):
    zero_vector = tuple(0 for i in range(n))
    res = [v for v in product([1, 0, -1], repeat = n) if v != zero_vector]
    return res

def v3_to_num(v):
    base = 3
    a = 1
    res = 0
    n = len(v)
    for i in range(n):
        res += a * (1 - v[n - 1 - i])
        a *= base
    if (res > (a - 1) / 2):
        res -= 1
    return res

def get_peak_point(n):
    res = tuple(3**i for i in range(n))
    return res

def get_pos_vectors(point, vectors):
    res = [v for v in vectors if get_sp(point, v) > 0]
    return res

def get_base_simplex(n):
    vertexes = []
    for i0 in range(1, n + 1):
        vertexes.append(tuple(0 for i1 in range(n - i0)) + tuple(1 for i1 in range(i0)))
    facets = []
    for i0 in range(n - 1):
        facet = tuple(0 for i1 in range(n - i0 - 2)) + (-1, 1) + tuple(0 for i1 in range(i0))
        facets.append(facet)
    facets.append((1,) + tuple(0 for i in range(n - 1)))
    return facets, vertexes

def get_is_crossing_vertexes(section_v, vertexes):
    is_neg = 0
    is_pos = 0
    for vertex in vertexes:
        sp = get_sp(vertex, section_v)
        if sp < 0:
            is_neg = 1
            if is_pos:
                return 1
        elif sp > 0:
            is_pos = 1
            if is_neg:
                return 1
    return 0

def get_int_hyperplane_line_intersection(h, p0, p1):
    coeff0 = get_sp(p0, h)
    coeff1 = -get_sp(p1, h)
    if coeff0 == -coeff1:
        p = None
    else:
        p = sum_lists([mul_list(p0, coeff1), mul_list(p1, coeff0)])
    return p, coeff0, coeff1

def get_mcc2_point(n):
    point = [i + 1 for i in range(n)]
    point[-1] += 1 / 2
    return point

def printl(s_list, *args):
    print(*args)
    for arg in args:
        s_list.append(str(arg) + " ")
    s_list.append("\n")

def print_div_tree(n, tree, max_level = None, file_name = None, strs = [], level = -1):
    if max_level is not None and level > max_level:
        return
    tabs = level * "  "
    if level >= 0:
        if len(tree) > 0:
            printl(strs, tabs + str(level) + "  " + str(tree[0]))
    else:
        print()
    for div in tree[1 : ]:
        for sub in div[1 : ]:
            print_div_tree(n, sub, max_level, file_name, strs, level + 1)
    if level == -1:
        if file_name is not None:
            strs_to_file(strs, file_name)

def get_sub_regions(n, facets, vertexes, crossing_v, is_both = 1):
    all_sps = [[get_sp(f, x) for f in facets] for x in vertexes]
    zero_v = tuple(0 for i in range(n))
    crossing_v_incidence_nums = []
    crossing_v_sps = []
    for x_num, x in enum(vertexes):
        sp = get_sp(x, crossing_v)
        crossing_v_sps.append(sp)
        x_sps = all_sps[x_num]
        if sp == 0:
            incidence_nums = set([f_num for f_num in nums(facets) if x_sps[f_num] == 0])
            crossing_v_incidence_nums.append(incidence_nums)
    new_x_incidence_nums_dict = {}
    for x1_num in range(1, len(vertexes)):
        x1 = vertexes[x1_num]
        if crossing_v_sps[x1_num] == 0:
            continue
        x1_sps = all_sps[x1_num]
        facet_nums1 = {}
        for f_num in nums(facets):
            if x1_sps[f_num] == 0:
                facet_nums1[f_num] = None
        for x0_num in range(x1_num):
            x0 = vertexes[x0_num]
            if crossing_v_sps[x0_num] * crossing_v_sps[x1_num] >= 0:
                continue
            x0_sps = all_sps[x0_num]
            common_f_nums = tuple(f_num for f_num in facet_nums1 if x0_sps[f_num] == 0)
            if len(common_f_nums) < n - 2:
                continue
            new_x, coeff0, coeff1 = get_int_hyperplane_line_intersection(crossing_v, x0, x1)
            if new_x is None or coeff0 * coeff1 <= 0:
                continue
            new_x_gcd = get_list_gcd(new_x)
            new_x = tuple(elt // new_x_gcd for elt in new_x) # ***
            if new_x < zero_v:
                new_x = mul_list(new_x, -1)
            new_x_incidence_nums = set([f_num for f_num in nums(facets) if get_sp(facets[f_num], new_x) == 0])
            is_found = 1
            for incidence_nums in crossing_v_incidence_nums:
                if new_x_incidence_nums.issubset(incidence_nums):
                    is_found = 0
                    break
            if not is_found:
                continue
            for new_x0 in list(new_x_incidence_nums_dict):
                new_x_incidence_nums0 = new_x_incidence_nums_dict[new_x0]
                if new_x_incidence_nums.issubset(new_x_incidence_nums0):
                    is_found = 0
                    break
                if new_x_incidence_nums0.issubset(new_x_incidence_nums):
                    del new_x_incidence_nums_dict[new_x0]
            if not is_found:
                continue
            new_x_incidence_nums_dict[new_x] = new_x_incidence_nums
    new_vertexes = list(new_x_incidence_nums_dict)
    sub_vertexes_record = [None, new_vertexes[:], new_vertexes[:]]
    crossing_vertex_nums_record = [None, [], []]
    for x_num, x in enum(vertexes):
        sp = crossing_v_sps[x_num]
        if sp >= 0:
            sub_vertexes_record[1].append(x)
            if sp > 0:
                crossing_vertex_nums_record[1].append(x_num)
        if sp <= 0:
            sub_vertexes_record[-1].append(x)
            if sp < 0:
                crossing_vertex_nums_record[-1].append(x_num)
    sub_facets_record = [None, [], []]
    res = []
    for sign_ in (1, -1):
        sub_facets_record[sign_].append(mul_list(crossing_v, sign_))
        for f_num, f in enum(facets):
            for x_num in crossing_vertex_nums_record[sign_]:
                if all_sps[x_num][f_num] == 0:
                    sub_facets_record[sign_].append(f)
                    break
        sub_r = [sub_facets_record[sign_], sub_vertexes_record[sign_]]
        if not is_both:
            res = sub_r
            break
        res.append(sub_r)
    return res

def rec_divide_ha2_by_vectors_3_part(n, vs, path, facet_nums, vertexes, all_crossing_vs, crossing_v_nums, depth_limit, iter_box, depth_box, tree, is_tree_used, facets_dict):
    div_count = 0
    depth = depth_box[0]
    region_records = []
    facets = [vs[f_num] for f_num in facet_nums]
    all_sub_regions = []
    sign_to_pos_dict = {1: 0, -1: 1}
    for div_v_num_num, div_v_num in enum(crossing_v_nums):
        crossing_v = all_crossing_vs[div_v_num]
        sub_regions = get_sub_regions(n, facets, vertexes, crossing_v)
        vector_div_count = 1
        subtree = [None, [], []]
        for sign_ in [1, -1]:
            pos = sign_to_pos_dict[sign_]
            [sub_facets, sub_vertexes] = sub_regions[pos]
            sub_vertexes.sort()
            sub_crossing_v_nums = [v_num for v_num in crossing_v_nums if get_is_crossing_vertexes(all_crossing_vs[v_num], sub_vertexes)]
            sub_path = path + [[crossing_v, div_v_num_num, len(crossing_v_nums), sign_]]
            sub_facet_nums = [v3_to_num(f) for f in sub_facets]
            sub_facet_nums.sort()
            sub_div_count = rec_divide_ha2_by_vectors_3(n, vs, sub_facet_nums, sub_vertexes, all_crossing_vs, sub_crossing_v_nums, depth_limit, iter_box, depth_box, subtree[sign_], facets_dict, sub_path)
            vector_div_count *= sub_div_count
            if sub_div_count == 0:
                break
        if sub_div_count == 0:
            continue
        div_count += vector_div_count
        if is_tree_used:
            if vector_div_count > 0:
                tree.append(subtree)
    return div_count

def rec_divide_ha2_by_vectors_3(n, vs, facet_nums, vertexes, all_crossing_vs, crossing_v_nums, depth_limit, iter_box, depth_box, tree, facets_dict, path):
    iter_box[0] += 1
    iter = iter_box[0]
    depth_box[0] += 1
    depth = depth_box[0]
    depth_diff = depth_limit - depth
    print_iter_count = 10**5
    is_tree_used = 1
    is_facets_reused = 1 #
    if is_facets_reused:
        facet_nums_key = ','.join(str(num) for num in facet_nums)
        if facet_nums_key in facets_dict:
            depth_record = facets_dict[facet_nums_key]
            if depth_record[0] >= depth_diff:
                div_count = 0
            elif depth_record[1] <= depth_diff:
                div_count = 1
            else:
                div_count = None
        else:
            depth_record = [-2, 10**6]
            facets_dict[facet_nums_key] = depth_record
            div_count = None
    else:
        div_count = None
    nzs = [v_num for v_num in crossing_v_nums if not 0 in all_crossing_vs[v_num]]
    if is_tree_used:
        path_elt = path[-1]
        tree.append([tuple(path_elt), len(nzs)])
    if iter % print_iter_count == 0 and iter > 0:
        print()
        print("iter, depth, len(nzs) =", iter, depth, len(nzs))
        print("path =", path)
    if div_count is None:
        if depth > depth_limit:
            div_count = 0
        if div_count is None:
            if len(nzs) == 0:
                div_count = 1
            else:
                div_count = rec_divide_ha2_by_vectors_3_part(n, vs, path, facet_nums, vertexes, all_crossing_vs, crossing_v_nums, depth_limit, iter_box, depth_box, tree, is_tree_used, facets_dict)
        if is_facets_reused:
            if div_count == 0 and depth_record[0] < depth_diff:
                depth_record[0] = depth_diff
            elif div_count > 0 and depth_record[1] > depth_diff:
                depth_record[1] = depth_diff
    depth_box[0] -= 1
    return div_count

def divide_ha2_by_vectors_3(n, depth_limit):
    vs = get_vectors_3(n)
    peak_point = get_peak_point(n)
    pos_vs = get_pos_vectors(peak_point, vs)
    pos_vs.sort()
    facets, vertexes = get_base_simplex(n)
    facet_nums = [v3_to_num(facet) for facet in facets]
    facet_nums.sort()
    vertexes.sort()
    all_crossing_vs = [v for v in pos_vs if get_is_crossing_vertexes(v, vertexes)]
    crossing_v_nums = list(nums(all_crossing_vs))
    tree = [] # [top, sub 1, sub -1]
    facets_dict = {}
    path = [[]]
    iter_box = [-1]
    depth_box = [-1]
    div_count = rec_divide_ha2_by_vectors_3(n, vs, facet_nums, vertexes, all_crossing_vs, crossing_v_nums, depth_limit, iter_box, depth_box, tree, facets_dict, path)
    print_div_tree(n, tree)
    print("div_count =", div_count)

def build_tree(n, depth_limit, vs):
    peak_point = get_peak_point(n)
    pos_vs = get_pos_vectors(peak_point, vs)
    pos_vs.sort()
    pos_vs2 = [v for v in pos_vs if not 0 in v]
    v_dict = {}
    for v_num, v in enum(vs):
        v_dict[v] = v_num
    fs, xs = get_base_simplex(n)
    x_list = xs[:]
    x_nums = tuple(i for i in nums(xs))
    x_dict = {}
    for x_num, x in enum(xs):
        x_dict[x] = x_num
    crossing_v_nums = [v_dict[v] for v in pos_vs if get_is_crossing_vertexes(v, xs)]
    crossing_v_nums.sort()
    print("len(crossing_v_nums) =", len(crossing_v_nums))
    r_num = 0
    f_nums = [v_dict[f] for f in fs]
    f_nums.sort()
    f_nums = tuple(f_nums)
    r_dict = {f_nums: r_num}
    r_list = [[f_nums, x_nums, crossing_v_nums]]
    [f_nums_pos, x_nums_pos, crossing_v_nums_pos] = nums(r_list[0])
    crossing_v_counts = [len(r_list[0][crossing_v_nums_pos])]
    parents_list = [[]]
    cur_r_nums = []
    next_r_nums = []
    next_todo_r_nums = [0]
    for depth in range(depth_limit):
        print()
        print("depth =", depth)
        todo_r_nums = next_todo_r_nums
        print("len(todo_r_nums) =", len(todo_r_nums))
        next_todo_r_nums = []
        for r_num_num, r_num in enum(todo_r_nums):
            if r_num_num % 10**4 == 0:
                print("r_num_num =", r_num_num)
                print("r_list[-1] =", r_list[-1])
            [f_nums, x_nums, crossing_v_nums] = r_list[r_num]
            fs = [vs[f_num] for f_num in f_nums]
            xs = [x_list[x_num] for x_num in x_nums]
            for crossing_v_num_num, crossing_v_num in enum(crossing_v_nums):
                crossing_v = vs[crossing_v_num]
                sub_regions = get_sub_regions(n, fs, xs, crossing_v)
                for sign_num in (0, 1):
                    [sub_fs, sub_xs] = sub_regions[sign_num]
                    sub_f_nums = [v_dict[f] for f in sub_fs]
                    sub_f_nums.sort()
                    sub_f_nums = tuple(sub_f_nums)
                    sub_parent = [r_num, crossing_v_num_num] #
                    if sub_f_nums in r_dict:
                        sub_r_num = r_dict[sub_f_nums]
                        parents_list[sub_r_num].extend(sub_parent) #
                        continue
                    sub_r_num = len(r_list)
                    sub_x_nums = []
                    for x in sub_xs:
                        if x in x_dict:
                            x_num = x_dict[x]
                        else:
                            x_num = len(x_list)
                            x_list.append(x)
                            x_dict[x] = x_num
                        sub_x_nums.append(x_num)
                    sub_x_nums.sort()
                    sub_x_nums = tuple(sub_x_nums)
                    sub_crossing_v_nums = [v_num for v_num in crossing_v_nums if get_is_crossing_vertexes(vs[v_num], sub_xs)]
                    is_leaf = 1
                    for v_num in sub_crossing_v_nums:
                        if not 0 in vs[v_num]:
                            is_leaf = 0
                            break
                    if is_leaf:
                        cur_r_nums.append(sub_r_num)
                    else:
                        if depth == depth_limit - 1:
                            next_r_nums.append(sub_r_num)
                        else:
                            next_todo_r_nums.append(sub_r_num)
                    sub_r = [sub_f_nums, sub_x_nums, sub_crossing_v_nums]
                    r_list.append(sub_r)
                    parents_list.append(sub_parent)
                    crossing_v_counts.append(len(sub_crossing_v_nums))
                    r_dict[sub_f_nums] = sub_r_num
    return parents_list, cur_r_nums, next_r_nums, crossing_v_counts

def divide_ha2_by_vectors_3_breadth_first(n, depth_limit):
    print("n, depth_limit =", n, depth_limit)
    vs = get_vectors_3(n)
    parents_list, cur_r_nums, next_r_nums, crossing_v_counts = build_tree(n, depth_limit, vs)
    sub_r_counts_list = [[0 for i in range(crossing_v_counts[count_num])] for count_num in nums(crossing_v_counts)]
    heights = [-1 for i in nums(crossing_v_counts)]
    print()
    for height in range(depth_limit + 1):
        for r_num in cur_r_nums:
            parents = parents_list[r_num]
            for parent_num in range(len(parents) // 2):
                parent_r_num = parents[2 * parent_num]
                if heights[parent_r_num] == -1:
                    div_num = parents[2 * parent_num + 1]
                    sub_r_counts_list[parent_r_num][div_num] += 1
                    if sub_r_counts_list[parent_r_num][div_num] == 2:
                        heights[parent_r_num] = height + 1
                        next_r_nums.append(parent_r_num)
        cur_r_nums = next_r_nums
        next_r_nums = []
    tree_depth = heights[0]
    if tree_depth <= depth_limit:
        print("tree_depth =", tree_depth)
    else:
        print("tree_depth >=", tree_depth)

def to_str(l):
    res = ','.join(str(elt) for elt in l)
    return res

def from_str(s):
    res = tuple(int(elt) for elt in s.split(","))
    return res

def rnd(n):
    return randint(0, n - 1)

def rnd_sign():
    return rnd(2) * 2 - 1

def rec_separate_point(n, p, depth_limit, pos_vs3, facets, vertexes, crossing_nz_v_nums, crossing_z_v_nums, v_dict, iter_box, path, prev_v_num, crossing_v_num_dict):
    depth = len(path)
    is_found = 0
    if len(crossing_nz_v_nums) <= 2:
        if depth_limit - depth >= len(crossing_nz_v_nums):
            res_height = len(crossing_nz_v_nums)
            found_depth = depth + len(crossing_nz_v_nums)
            print("found_depth =", found_depth)
        else:
            res_height = None
        is_found = 1
    else:
        if len(crossing_nz_v_nums) == 3 and depth >= depth_limit - 1 or len(crossing_nz_v_nums) >= 4 and depth >= depth_limit - 2 or len(crossing_nz_v_nums) >= 8 and depth >= depth_limit - 3 or len(crossing_nz_v_nums) >= 16 and depth >= depth_limit - 4: #
            res_height = None
            is_found = 1
    if not is_found:
        sub_rs = []
        res_height = None
        for crossing_v_num in crossing_nz_v_nums + crossing_z_v_nums:
            if crossing_v_num <= prev_v_num:
                continue
            crossing_v = pos_vs3[crossing_v_num]
            [sub_facets, sub_vertexes] = get_sub_regions(n, facets, vertexes, crossing_v, 0)
            crossing_v_count = 0
            for f in sub_facets:
                if v_dict[f] in crossing_v_num_dict:
                    crossing_v_count += 1
            if crossing_v_count != depth + 1:
                sub_rs = None
                break
            sub_rs.append([sub_facets, sub_vertexes, crossing_v_num])
        if sub_rs is not None:
            path.append(0.0)
            for sub_r_num, [sub_facets, sub_vertexes, crossing_v_num] in enum(sub_rs):
                crossing_v = pos_vs3[crossing_v_num]
                path[-1] = sub_r_num / len(sub_rs)
                iter_box[0] += 1
                if iter_box[0] % 10**4 == 0:
                    print("path =", [round(elt, 3) for elt in path])
                sub_crossing_nz_v_nums = [v_num for v_num in crossing_nz_v_nums if get_is_crossing_vertexes(pos_vs3[v_num], sub_vertexes)]
                sub_crossing_z_v_nums = [v_num for v_num in crossing_z_v_nums if v_num > prev_v_num and get_is_crossing_vertexes(pos_vs3[v_num], sub_vertexes)]
                sub_height = rec_separate_point(n, p, depth_limit, pos_vs3, sub_facets, sub_vertexes, sub_crossing_nz_v_nums, sub_crossing_z_v_nums, v_dict, iter_box, path, crossing_v_num, crossing_v_num_dict)
                if sub_height is not None:
                    if res_height is None:
                        res_height = sub_height + 1
                    else:
                        res_height = min(res_height, sub_height + 1)
            path.pop()
    return res_height

def separate_point(p, depth_limit, pos_vs3, v_dict, iter_box, path):
    n = len(p)
    facets, vertexes = get_base_simplex(n)
    crossing_nz_v_nums = [v_num for v_num in nums(pos_vs3) if not 0 in pos_vs3[v_num] and get_is_crossing_vertexes(pos_vs3[v_num], vertexes)]
    crossing_z_v_nums = [v_num for v_num in nums(pos_vs3) if 0 in pos_vs3[v_num] and get_is_crossing_vertexes(pos_vs3[v_num], vertexes)]
    prev_v_num = -1
    crossing_v_num_dict = {}
    for v_num in crossing_nz_v_nums + crossing_z_v_nums:
        crossing_v_num_dict[v_num] = None
    depth = rec_separate_point(n, p, depth_limit, pos_vs3, facets, vertexes, crossing_nz_v_nums, crossing_z_v_nums, v_dict, iter_box, path, prev_v_num, crossing_v_num_dict)
    return depth

def separate_mcp2(n, depth_limit):
    vs2 = get_vectors_2(n)
    vs3 = get_vectors_3(n)
    p = get_rnd_mcc2_point(n)
    pos_vs3 = get_pos_vectors(p, vs3)
    pos_vs3.sort(key = lambda v: [v.count(0), v])
    v_dict = get_vector_dict(pos_vs3)
    iter_box = [0]
    path = []
    depth = separate_point(p, depth_limit, pos_vs3, v_dict, iter_box, path)
    print("depth =", depth)

#separate_mcp2(7, 7)
#divide_ha2_by_vectors_3_breadth_first(5, 10)
divide_ha2_by_vectors_3(5, 3)

Answer 2

There are several reasons to believe $P \neq NP$.

1) This is usually the answer given when first introducing P and NP. At present, there are thousands of NP-Complete problems across virtually every technical discipline impacted by computing- combinatorics, number theory, geometry, economics and finance, biology, operations research, etc. A lot of these problems bare no obvious relation to each other, besides the fact that they are NP-Complete. Since 1971, nobody has been able to find an NP-Complete problem that is in P. Note that a polynomial time solution to one NP-Complete problem yields a polynomial time solution to all NP-Complete problems. Given the vast number of unrelated NP-Complete problems, this is strong evidence (not proof) that P and NP are different.

2) Ladner's Theorem states that if P and NP are different, then there exists an NP-Intermediate problem (that is, a problem in NP that is not in P and not NP-complete). Actually, Ladner's Theorem gives us infinitely many such problems. The Wikipedia page lists several examples of candidate NP-Intermediate problems (https://en.wikipedia.org/wiki/NP-intermediate). The factoring problem is a popular example. Group Isomorphism is another good example. Nobody has shown that Group Isomorphism is NP-Complete. However, except in specific cases (e.g., groups with Abelian Sylow towers), the $O(n^{\log(n)})$ bound is still (to the best of my knowledge) about the best we know how to do.

3) If P = NP, then the polynomial time hierarchy collapses. An open conjecture states that each class in the polynomial time hierarchy is distinct, and most complexity theorists believe this to be true. Consider the Independent Set problem, which we know to be NP-Complete. Now the Maximum Independent Set problem is of the form: $$\{ \langle G, k \rangle : \text{ the largest independent set in G has k vertices } \}$$

The Maximum Independent Set problem is in $\Sigma_{2}^{p}$. Given a largest independent set, we can verify by examining all subsets of vertices of $G$ that there is no other independent set with more than $k$ vertices. Certainly, the Maximum Independent Set problem could be in NP. However, there is no reason to believe the Maximum Independent Set problem is in NP. Could you find a single certificate of reasonable length (length polynomial in $|G|$) that verifies $G$ contains an independent set of size $k$, and no other independent set is larger? There could be exponentially many independent sets in $G$.