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 

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()