Express a number as sum of 2 primes Problem: Given an even number (greater than 2), return two prime
  numbers whose sum will be equal to given number.
  
  NOTE 1:  A solution will always exist. (Goldbach's conjecture)
  
  Note 2: If there are more than one solutions possible, return the
  lexicographically smaller solution.


This solution becomes slower for higher order numbers. How can I optimise this code?

import math
# Function to create a list of all prime numbers uptil given number
def list_prime(A):
    primes = []  # initialise an empty list of primes
    bool_a = [True for i in range(2,A+3)]  # creates boolean list of index 
    for  i in range(2, int(math.sqrt(A))+1):  
        if bool_a[i]:
            for j in range( i * i, A +1 , i):  # eliminate all multiples of i*i+i, i*i+2i and so on uptil A+1    
                if bool_a[j]:
                    bool_a[j] = False;

    for i in range(2,A):  # the index of reamaining bools are prime numbers 
        if bool_a[i]:
            primes.append(i)

    return primes

#Function that returns two prime numbers whose sum is equal to the given number
def prime_sum(A):
    solution_set = []

    for i in (list_prime(A)):
        for j in (list_prime(A)[::-1]):
            if i + j == A:
                solution_set.append((i,j))
                break

    return min(solution_set)
Using the Sieve of Eratosthenes seems like a reasonable way to generate a large number of primes. 

One thing that you could do is directly return your bitset representation of the primes, rather than copying it to a condensed list. This would save a bit of time in the short term, and be helpful for the next step.



for i in (list_prime(A)):
    for j in (list_prime(A)[::-1]):


A few comments. 

First, doing something twice is slower than doing it once! Since list_prime(A) is repeated in both lines, it will have to re-run the Sieve of Eratosthenes: even though you know that the list of prime numbers isn't going to change, Python doesn't! Even worse, because the second line is in a loop, you're running list_prime again for every value of i. So you can speed it up a bit by storing that list in a variable before you get to the loops.

Second, when you have nested loops like this, you make your algorithm quadratic in the size of list_prime(A). The issue is that you're doing the imprecise test for j before the precise test, which is normally the slow way around. That is, you're considering all the values of j which meet the rule "j is a prime number" and then testing whether "j + i == A". Instead consider all the values of j for which "j + i == A" first. There is exactly one of those for each i, which is found by simple subtraction. Then check whether that j is in your list of prime numbers. If so, you have a match. If not, you can immediately check the next i.

(The reason that I suggested returning the bitset representation of the list of primes is that it makes it much faster to check whether a specific number is prime.)



A few less substantial optimisations

solution_set.append((i,j))


It is good to consider the tie-breaking rules for problems like this, and listing candidates first and checking which wins afterwards is a valid way to do so. 

However, it is worth thinking about the order of your algorithm before implementing the tie-breaking check. If, as is the case here, the first satisfying value is guaranteed to be the one that wins the tie break because it has the smallest i value, you might as well just return the first one you get to. 



if bool_a[j]:
    bool_a[j] = False;


If the end result of these two lines is that bool_a[j] must be False, just set it to false. if statements are surprisingly slow on modern CPUs. 



primes.append(i)


Whenever you find yourself appending something to a list one element at a time, consider whether you can rewrite it using list comprehensions. For example something like the following:

primes = [index for (index, is_prime) in enumerate(bool_a) if is_prime]


(However, as above, my actual recommendation is that you completely remove that step and directly return bool_a)