Appellant James R. Fristoe appeals from the district court’s order denying his petition for a writ of habeas corpus pursuant to 28 U.S.C. § 2241. ^[1] The issue to be resolved in this appeal is whether a prisoner convicted of a nonviolent drug offense, whose sentence was enhanced for possession of a firearm, is categorically disqualified from receiving a sentence reduction made available only to prisoners convicted of “nonviolent offenses.” See 18 U.S.C. § 3621(e)(2)(B). The district court concluded that the Bureau of Prisons (BOP) acted permissibly in adopting an interpretation of the statute which examines sentencing factors as well as the crime of conviction in determining whether an inmate is eligible for the sentence reduction. We reverse.

I.

Appellant is presently incarcerated, serving an eighty-four month sentence imposed on February 7, 1994, after he pled guilty to conspiracy to distribute cocaine base and cocaine in violation of 21 U.S.C. §§ 841(a)(1), 841(b)(1)(A), and 846. At sentencing, he received a two-level sentence enhancement for possession of a firearm during the course of a drug trafficking conspiracy. See U.S.S.G. § 201.1(b)(1).

In his petition, appellant contends that the BOP has wrongfully denied him eligibility for a sentence reduction for his successful completion of a drug treatment program under 18 U.S.C. § 3621(e)(2)(B) of the Violent Crime Control and Law Enforcement Act of 1994. The Act provides in pertinent part:

(2) Incentive for prisoners’ successful completion of treatment program.—

(B) Period of custody.—The period a prisoner convicted of a nonviolent offense remains in custody after successfully completing a treatment program may be reduced by the Bureau of Prisons, but such reduction may not be more than one year from the term the prisoner must otherwise serve.

18 U.S.C. § 3621(e)(2)(B).

The statute does not define a “nonviolent offense.” The BOP has established a regulation, however, which implements that qualification by excluding persons whose current offense is a “crime of violence,” as that term is defined in the Criminal Code at 18 U.S.C. § 924(c)(3). ^[2] The version of this regulation in effect at the time of appellant’s application stated as follows:

An inmate who completes a residential drug abuse treatment program during his or her current commitment may be eligible for early release by a period not to exceed 12 months, in accordance with paragraph (a) of this section ... unless the inmate’s current offense is determined to be a crime of violence as defined in 18 U.S.C. § 924(c)(3).

28 C.F.R. § 550.58 (1995).

The BOP has further determined the scope of the-term “crime of violence” through issuance of its Program Statement 5162.02. Section 9 of the Program Statement provides that convictions, like appellant’s, obtained under 21 U.S.C. § 841 or § 846, should be considered convictions for a “crime of violence” if the sentencing court increased the base level of the sentence for possession of a dangerous weapon during the commission of[*630] the offense. Under the rationale of the Program Statement and the regulation, then, appellant’s crime was not a “nonviolent offense,” because of the sentencing enhancement, and he was therefore ineligible for the sentence reduction.

II.

Appellant’s entitlement to relief depénds on his showing that “[h]e is in custody in violation of the Constitution or laws or treaties of the United States.” 28 U.S.C. § 2241(c)(3). Appellant presents several constitutional arguments to satisfy this predicate. We consider each of these claims in turn.

Appellant first raises a claim under the; Due Process Clause. To make out a due process claim, appellant must assert the infringement of a protected liberty interest. See Kentucky Dep’t of Corrections v. Thompson, 490 U.S. 454, 460, 109 S.Ct. 1904, 1908, 104 L.Ed.2d 506 (1989). A protected liberty interest may arise from either the Due Process Clause itself, or from a state or federal law. See id.; cf. Miller v. Federal Bureau of Prisons, 989 F.2d 420, 423 n. 4 (10th Cir.1993) (noting rule in circuits holding former federal parole statute created liberty interest).

The Constitution does not itself afford appellant a liberty interest in a reduced sentence. A convicted person has no constitutional or inherent right to be conditionally released before the expiration of a valid sentence. See Greenholtz v. Inmates of Nebraska Penal & Correctional Complex, 442 U.S. 1, 7, 99 S.Ct. 2100, 2103-04, 60 L.Ed.2d 668 (1979).

Neither does § 3621(e)(2)(B) create a liberty interest. It states that the inmate’s sentence “may be reduced by the Bureau of Prisons.” (emphasis added). A statute which allows a decisionmaker to deny the requested relief within its unfettered discretion does not create a constitutionally-recognized liberty interest. See Olim v. Wakinekona, 461 U.S. 238, 249, 103 S.Ct. 1741, 1747-48, 75 L.Ed.2d 813 (1983). Appellant’s due process claim fails, therefore, because he has not demonstrated that he has a liberty interest in the sentence reduction which he seeks.

Appellant next claims that the failure to grant him a sentence reduction violates the Ex Post Facto Clause of the Constitution. He argues that since he entered the rehabilitation program before the BOP promulgated its definition of a “crime of violence,” that definition cannot now be applied to him. There is no ex post facto violation here, because, the challenged regulation did not affect the legal consequences of appellant’s crime or increase his punishment. See Stiver v. Meko, 130 F.3d 574, 578 (3d Cir.1997) (rejecting similar argument).

Finally, appellant argues that the BOP’s refusal to consider him for sentence reduction violates the Equal' Protection Clause. He notes that the BOP has acquiesced in a Ninth Circuit case invalidating its interpretation of § 3621(e)(2)(B) under similar circumstances. See Downey v. Crabtree, 100 F.3d 662, 671 (9th Cir.1996). Contrary to appellant’s contentions, however, the BOP is not compelled by equal protection principles to acquiesce nationwide in the Ninth Circuit’s decision. See Castillo-Felix v. INS, 601 F.2d 459, 467 (9th Cir.1979) (INS was not compelled by equal protection principles to obey holding of Second Circuit Court of Appeals. outside the Second Circuit). “It is elementary that decisions of one Court of Appeals cannot bind another.” Id. Under our legal system, authoritative decisions of that nature aré left to the United States Supreme Court.

HI.

Although appellant’s constitutional arguments are unavailing, our work is not finished. His pro se complaint also raised the issue of whether the BOP has adopted a permissible construction of the statute.

In his answer brief, appellee asserts that review of BOP decisions under § 3621(e)(2)(B) is not available under the Administrative Procedure Act (APA). See 18 U.S.C. § 3625. While § 3625 may preclude us from reviewing the BOP’s substantive decision in appellant’s case, it does not prevent us from interpreting the statute to determine[*631] whether the BOP exceeded its statutory' authority. See, e.g., Martin v. Gerlinski, 133 F.3d 1076, 1079 (8th Cir.1998); Roussos v. Menifee, 122 F.3d 159, 163 (3d Cir.1997).

We recently discussed the analysis we follow when examining the agency’s construction of a statutory term. See Southern Ute Indian Tribe v. Amoco Prod. Co., 119 F.3d 816, 830-36 (10th Cir.1997). We begin by asking whether Congress has “directly spoken to the precise question at issue.” Id. at 830 (further quotation omitted). Congress has not defined a “nonviolent offense” for purposes of this statute.

We next ask whether Congress has delegated to the agency the responsibility to address the question. See id. at 831. It is undisputed that the BOP has been delegated the authority to interpret § 3621(e)(2)(B). However, we must also ask whether this delegation of authority carries with it the discretion to interpret the statute with the force of law utilizing the particular format at issue, i.e., a program statement. See Southern Ute Indian Tribe, 119 F.3d at 832. An agency’s interpretation of a statute by formal regulation or adjudication is entitled to deference, so long as the agency’s interpretation is based upon a permissible construction of the statute. See Chevron, U.S.A., Inc. v. Natural Resources Defense Council, Inc., 467 U.S. 837, 843, 104 S.Ct. 2778, 2781-82, 81 L.Ed.2d 694 (1984). Where the agency’s interpretation of the statute is made informally, however, such as by a “program statement,” the interpretation is not entitled to Chevron deference, but will instead be considered only to the extent that it is well-reasoned and has “power to persuade.” See Southern Ute Indian Tribe, 119 F.3d at 834.

We begin by noting that courts typically do not consider the predicate drug offense here, conspiracy to distribute cocaine, a “crime of violence.” See, e.g., United States v. Diaz, 778 F.2d 86, 88 (2d Cir.1985) (holding, under former version of 18 U.S.C. § 924(c), that drug conspiracy was not a “crime of violence”). The BOP’s classification of appellant’s offense as a “crime of violence,” therefore, must rest entirely upon consideration of sentencing factors which are not implicated categorically by the nature of his underlying offense.

Reliance on sentencing enhancements, however, conflicts with the plain language of the statute. Section 3621(e)(2)(B) refers to prisoners “convicted of a nonviolent offense.” (emphasis added). The statute does not permit resort to sentencing factors or sentencing enhancements attached to the nonviolent offense.

In United States v. Wagner, 994 F.2d 1467, 1474 (10th Cir.1993), we considered whether the government could use relevant conduct to classify a violation of 21 U.S.C. § 841(d) as a “controlled substance offense,” for purposes of a career offender provision, U.S.S.G. § 4B1.1. We noted that an “offense,” for purposes of the sentencing guidelines, usually includes all relevant conduct. See Wagner, 994 F.2d at 1474. However, since the specific definition of “controlled substance offense” employed in U.S.S.G. § 4B1.2(2) referred directly to the charged offense, rather than to all relevant conduct, resort to the relevant conduct was not permitted. See id.

The same is true here. The eligibility criteria in 18 U.S.C. § 3621(e)(2)(B) refer directly to the offense for which the prisoner was convicted. The BOP’s program statement definition of a “nonviolent offense” is not well-reasoned, and fails to persuade us that it is entitled to deference. The BOP’s interpretation violates the plain language of the statute and cannot be upheld.

We are joined in this view by the majority of circuits which have considered this question. See Martin, 133 F.3d 1076, 1079-81; Bush v. Pitzer, 133 F.3d 455, 456-57 (7th Cir.1997); Roussos, 122 F.3d 159, 161-64; Downey, 100 F.3d at 666-71; see also Sisneros v. Booker, 981 F.Supp. 1374, 1376-77 (D.Colo.1997). Only the Fifth Circuit has upheld the BOP’s program statement against a similar challenge. See Venegas v. Henman, 126 F.3d 760, 761-62 (5th Cir.1997), cert. denied, — U.S. -, 118 S.Ct. 1679, 140 L.Ed.2d 817 (1998).

In Venegas, noting the discretion given to the BOP in particular cases, the Fifth Circuit took the position that “the use of the phrase ‘a nonviolent offense’ merely excludes all in[*632] herently violent offenses from eligibility for consideration, while leaving to the Bureau’s discretion the determination of which other offenses will or will not be eligible for consideration.” 126 F.3d at 763 (emphasis added). In our view, this rationale avoids the central question: whether the BOP may treat a sentence ehhancement as though it were the “conviction” of such “other offense.” Unless this is permissible, the Fifth Circuit’s approach would permit the BOP to treat nonviolent offenders as though they were convicted of a violent offense, undermining the express language of the statute. We therefore find the Fifth Circuit’s approach unpersuasive. ^[3]

IV.

Having determined that the BOP exceeded its authority in categorically excluding from consideration inmates convicted of nonviolent offenses who received a sentencing enhancement for possession of a firearm, we move on to the appropriate relief to be granted in this case. Appellee correctly points out that we do not have authority to grant appellant the sentence reduction, because that decision rests with the BOP. Therefore, the judgment of the United States District Court for the Western District of Oklahoma is REVERSED and REMANDED to the district court for further remand to the Bureau of Prisons for further proceedings consistent with this opinion. The mandate shall issue forthwith.