app.py

from google import genai
from google.genai import types
import gradio as gr
import os



MODEL_ID = "gemini-2.0-flash-thinking-exp"
from google import genai
client = genai.Client(api_key=os.getenv('api_key'))

def llm_response(text):
  response = client.models.generate_content(
    model=MODEL_ID,
    contents= text)
  return response.text

def pvsnp(problem):
  classification = llm_response(f'''
You are an expert in computational complexity theory, specializing in both classical complexity classes (P, NP, NP-complete, NP-hard) and modern developments (e.g., parameterized complexity, fine-grained complexity, Minimum Circuit Size Problem).

Your task is to classify a given problem into one of the following categories:

P: Solvable in deterministic polynomial time.

NP: Verifiable in polynomial time.

NP-complete: Both in NP and NP-hard.

NP-hard: At least as hard as NP-complete problems, possibly outside NP.

Beyond NP: Likely in PSPACE, EXPTIME, or undecidable.

Other: Fits alternative complexity classes (e.g., BPP, co-NP).

Problem Description:
{problem}

If the given problem is a NP-hard problem,  decompose the NP-hard problem into polynomial-time solvable subproblems without solving them.

🔹 Inputs:
A formal definition and instance of the NP-hard problem (e.g., SAT, TSP, Graph Coloring).

Optional: Constraints or domain knowledge.

🔹 Decomposition Process:
Graph Representation & Structural Analysis

Convert the problem into a graph (if applicable).

Identify independent or tractable substructures.

Classification of Subproblems

Detect polynomially solvable parts (e.g., tree structures, bipartite graphs).

Separate them from harder components.

Partitioning & Transformation

Break the problem into independent or loosely connected subproblems.

Ensure each subproblem is in P or provably easier than the original.

Output a structured breakdown.

🔹 Outputs:
A list of P-complexity subproblems.

A dependency graph of their relationships in ASCII format.

A complexity analysis report quantifying decomposition effectiveness.

Guidelines for Classification:
Problem Analysis

Determine if the problem is a decision, optimization, or function computation problem.

Identify key input/output characteristics and constraints.

Complexity Insights

Check for polynomial-time solvability via known techniques (dynamic programming, greedy methods).

Assess reductions to/from well-studied problems.

Advanced Considerations

Incorporate recent research (e.g., MCSP's implications for NP-completeness).

Evaluate parameterized complexity (FPT results) and fine-grained complexity (SETH, other conjectures).

Consider probabilistic or average-case complexity aspects.

Justification

Provide a concise explanation for the classification, referencing key problem features and relevant research.

Your Classification and Explanation:
''')
  
  return classification

def critic_analysis(classification_output):
    critic = llm_response(f'''"You are PolyCritic, an expert in computational complexity and problem decomposition. Your goal is to critically evaluate whether a given
      NP-hard problem, when broken into P-solvable subproblems, can be efficiently recombined to yield the full solution. Here is the problem and the analysis: {classification_output}

Instructions:
1️⃣ Input: A decomposed NP-hard problem along with its P-solvable subproblems.
2️⃣ Step 1 - Validate Subproblems:

Do these subproblems fully cover the original problem?

Are they correctly categorized as P?
3️⃣ Step 2 - Analyze Recombination Complexity:

Can the subproblem solutions be combined in polynomial time?

If not, what is the bottleneck? (e.g., exponential merging, missing constraints)
4️⃣ Step 3 - Provide Verdict:

If recombination is efficient, explain why this suggests progress towards P = NP.

If inefficient, identify where complexity remains and suggest next steps.
5️⃣ Step 4 - Provide Complexity Insights:

Offer insights into whether certain structural patterns predict efficient recombination.

Suggest improvements in decomposition strategies.

Example Analysis Format:
💡 Problem: Traveling Salesperson (TSP)
🔍 Subproblems: Shortest paths between city clusters (P-solvable)
⚖ Recombination Complexity: Exponential growth in possible paths when merging clusters
🚨 Verdict: Recombination remains NP-hard → Decomposition needs refinement

👉 Your task is to apply this structured critique to any NP-hard problem and determine if it truly reduces to P.''')  
    return critic
    

'''
iface = gr.Interface(
    fn=pvsnp, 
    inputs=gr.Textbox(label="What problem would you like to classify as P or NP?"), 
    outputs=gr.Markdown(label="Agent's response"),  # Output as HTML
    title="PolyProb",
    description="PolyProb is an advanced AI agent that guides users through the intricate maze of computational complexity. This agent scrutinizes problem descriptions with sophisticated LLM prompts and symbolic reasoning. It classifies problems into categories such as P, NP, NP-complete, NP-hard, or beyond (e.g., PSPACE, EXPTIME), while providing clear, concise explanations of its reasoning. As part of AI Quotient’s Millennium Math Challenge, it is the first step towards solving the P vs NP problem.",
    theme = gr.themes.Ocean(),
    examples = ["Can you find a path that visits each node exactly once in a given graph?", "How efficiently can two nXn matrices be multiplied?", "Is there a subset of given numbers that sums to a target value?"]
)

# Launch the app
iface.launch() '''

with gr.Blocks(theme=gr.themes.Ocean()) as app:
    gr.Markdown("# PolyProb & PolyCritic AI 🤖")
    gr.Markdown('''PolyProb and PolyCritic are AI Agents that help users classify a problem into categories such as P, NP, NP-complete, NP-hard while 
    providing clear, concise explanations of its reasoning. As part of AI Quotient’s Millennium Math Challenge, it is the first step towards solving the P vs NP problem.''')
    
    with gr.Row():
        problem_input = gr.Textbox(label="Enter a computational problem")
        classify_button = gr.Button("Classify")
    
    classification_output = gr.Markdown(label="Classification (P or NP)")
    
    classify_button.click(pvsnp, inputs=problem_input, outputs=[classification_output])
    
    evaluate_button = gr.Button("Evaluate Recombination Complexity")
    recombination_output = gr.Textbox(label="Recombination Complexity")
    
    evaluate_button.click(critic_analysis, inputs=classification_output, outputs=recombination_output)
    
    #results_button = gr.Button("Show Stored Results")
    #results_display = gr.Textbox(label="Stored Results")
    
    #results_button.click(get_stored_results, outputs=results_display)

app.launch()